Cardiff skipper and captain David Marshall was sent off in the first half after tangling with Matt Derbyshire.
Vadis Odjidja-Ofoe converted the resulting penalty but Peter Whittingham scored from the spot minutes later to ensure it was 1-1 at half time.
Rotherham took until added on time to get their first three-pointer of the season through Matthew Connolly's own goal.
The home side had the first real opportunity from Joe Newell's corner but Danny Collins' header was blocked on its way to goal by Cardiff's Sean Morrison.
Morrison caused problems at the other end when he headed back a Whittingham free-kick across goal but the ball evaded everybody.
Tony Andreu then latched onto a loose ball and tested Marshall for the first time with a 25-yard effort.
The home side had a perfect opportunity to go ahead when a through ball caught Connolly out and Derbyshire was clean through, he tried to square for Jonson Clarke-Harris but the ball was just out of his reach.
The game's major talking point came four minutes before the break when Marshall, who had the ball in his hands, saw red after aiming a kick at Derbyshire following a coming together between the two. Referee Keith Hill dismissed the keeper and awarded Rotherham a penalty.
Following the commotion, and replacement keeper Simon Moore coming on for striker Joe Mason, Odjidja-Ofoe buried the chance into the bottom left corner.
But Cardiff ensured they went into the break level when Whittingham converted from the spot in added on time after Fabio Da Silva was fouled in the box by Farrend Rawson.
With the man advantage Rotherham created a host of chances to win the game. First, Clarke-Harris tested Moore with a volley.The same striker then headed over a cross from Newell.
Rotherham were enjoying the vast majority of the possession and should have gone back in front but Derbyshire could only guide Andre's headed pass into Moore's grasp from 10 yards out.
Both Joe Mattock and Collins tried their luck in a scramble following a corner.
Emmanuel Ledesma was brought on by Steve Evans and he produced a cross which Derbyshire diverted narrowly over the bar.
Rawson then fired over from just yards out from Derbyshire's cross and Clarke-Harris headed over another opportunity created by Newell.
Rotherham came within inches of grabbing the winner when Newell caught a volley perfectly but his shot cannoned back off the post and away to safety.
The winner did come in added on time when substitute Chris Maguire delivered a teasing cross into the near post which Connolly nudged past the helpless Moore.
Rotherham United: L Camp, L Buxton, J Mattock, D Collins (capt), J Clarke-Harris, F Rawson, J Newell, T Andreu (E Ledesma 68), V Odidja-Ofoe, M Derbyshire (C Maguire 82), R Smallwood. Subs not used: A Collin, D Ward, P Green, G Halford, G Ward.
Cardiff City: D Marshall (capt), L Peltier, S Morrison, M Connolly, S Malone, C Noone, K Dikgacoi, P Whittingham, J Ralls, J Mason (S Moore 42), S Ameobi (A Revell 86). Subs not used: S Moore (gk), B Manga, A Pilkington, A Gunnarsson, S Malone.
YELLOW CARDS
Rotherham: Joe Mattock (foul 15), Farrend Rawson (foul 45),
Cardiff: Sammy Ameobi (foul 19), Peter Whittingham (foul 24).
RED CARD
Cardiff: David Marshall (kicking out at Derbyshire, 43).
Referee: Keith Hill (Hertfordshire)
Attendance: 8,935 (818 away)