Wolves, with caretaker Stuart Gray in charge, were trailing until Kevin Cooper produced a wonder goal and Carl Cort grabbed the winner.
The defeat took Rotherham's dismal run to 19 league matches without a win and they are already odds-on favourites for the drop.
The Millers took the lead nine minutes before half-time when Martin McIntosh produced a towering header to beat Michael Oakes from Chris Sedgwick's text-book corner.
But Wolves could count themselves unlucky not to be on the score-sheet as a string of chances went begging for both sides.
Shaun Newton snapped in a first-time shot after Kevin Cooper's low cross from the right after just seven minutes but Mike Pollitt matched it with a low save to his right.
And when Pollitt missed his punch to a Cooper corner, Kenny Miller hoisted his close-range shot over the top from six yards.
Rotherham had to rely on a goal-line clearance after 28 minutes when Cooper powered through into the area and beat Pollitt but Shaun Barker cleared off the line and Michael Proctor hooked away the ball to safety.
And when Miller turned in another low cross from the right Newton drilled his shot wide.
Rotherham were boosted by the return of striker Martin Butler in the side for the first time this season after a summer bout of Hepatitis and glandular fever.
Butler linked up with Brazilian loan star Junior and gave Wolves early headaches. Oakes was forced to make an early save to deny Junior after he squeezed in a shot after a sharp turn.
And Oakes held on again when Proctor tried a shot from a tight angle. When Butler picked out Junior with an accurate crossfield pass the man on loan from Derby cut in and fired wide.
Wolves should have been level seven minutes into the second half when Colin Cameron burst into the area, shook off two challenges but fired wide as Pollitt raced off his line.
As Wolves set the pace Rotherham could have had a second goal with another corner but this time McIntosh headed over.
Wolves saw more chances go begging as Cameron sliced wide and then Miller was off target.
But in the 69th minute Cooper pounced as the home side backed off and he lashed in a shot that dipped over Pollitt and went in off the underside of the bar.
And substitute Ki-Hyeon Seol set up the winner when he slipped down the left 11 minutes from the end and drilled a low cross for Cort to slide his close-range shot past Pollitt.