Leeds, who made eight changes including leaving top marksman Jermaine Beckford on the bench, enjoyed most of the early possession as Robert Snodgrass stuck the top of the bar with a 25 yarder, but the Millers gradually came into things and took a 17th minute lead as Ian Sharps' header from a long Andy Nicholas throw looped over 'keeper David Lucas.
Mark Hudson then tried to test Lucas again in the 24th minute but his shot whilsted wide of the upright.
In turn the visitors pushed for an equaliser as Neil Kilkenny fired a 30 yarder wide of Andy Warrington's left post, and on the half hour they got their reward as Jonathon Howson converted after a goalmouth scramble as Rotherham failed to clear.
The Millers regained the lead though on the stroke of half time, as Reuben Reid was sent tumbling in the box after a juinking run. Mark Hudson's spotkick was saved but the midfielder pounced on the rebound to leave Lucas flat footed and send the home side into the break with a 2-1 advantage.
And they couldn't have started the second half any better as two powerful headers, first from Drewe Brouughton three minutes after the break from Dale Tonge's cross and then from an unmarked Nick Fenton five minutes later, gave them a comfortable 4-1 cushion.
Three minutes later though Enoch Showumni pulled a goal back by slotting under Warrington, with still over half an hour to play.
The Millers had to soak up some Leeds pressure, but the Elland Road outfit were wasteful in the final third.
Beckford and Becchio were introduced 20 minutes from time, but Rotherham coped admirably as defender Alan Sheehan limped off to leave Leeds playing out the final 10 or so minutes with only ten men after using their quota of substitutes.
The quest for a fifth goal was ruled out by referee Mathieson as Pablo Mills' header from Hudson's centre looped into the net, but Ian Sharps was penalised for impeding Lucas and it was chalked off, as Rotherham finished strongly and booked their place in the quarter final draw.
Millers: Warrington, Tonge, Fenton, Sharps, Nicholas, Cummins, Mills, Hudson, Rhodes, Reid, Broughton.
Subs Not Used: Cann, Burchill, Joseph, Taylor, Green.
Leeds: Lucas, Hughes, Marques, Michalik, Parker (Sheehan 57), Prutton, Kilkenny, Howson, Robinson (Becchio 71), Snodgrass, Showunmi (Beckford 71).
Subs Not Used: Ankergren, Delph
Att: 4,658
Ref: Scott Mathieson (Cheshire).