Two late goals gave Sabri Lamouchi his first victory as Cardiff City boss as they ended their run of 14 games without a win at St Andrew's.
In a game of few chances, Perry Ng's brilliant free-kick put Cardiff ahead.
The Bluebirds extended their lead in stoppage time when substitute Callum Robinson scored a solo effort to earn Cardiff a first win since 5 November.
The hosts, who rarely tested Cardiff goalkeeper Ryan Allsop, were booed off by their supporters at full-time.
Victory lifts Cardiff three points clear of the Championship relegation zone as they took advantage of a poor display from a consistently inconsistent Blues side who slip to 18th.
Birmingham were looking for a third successive win after following up their dramatic 4-3 victory at Swansea with a morale-boosting win against rivals West Brom.
Blues welcomed back midfielder Harlee Dean, as the 31-year old defender made a first start since 5 November in their only change.
Birmingham have a rotten record in recent years against the Bluebirds, having failed to beat them in eight league games, but they would have been encouraged by Cardiff's recent form.
Winless in 12 league games and above the Championship relegation zone only on goal difference, Cardiff were looking to address their chronic lack of goals, having previously found the net only 22 times in 31 league games.
Lamouchi named two strikers in his starting XI as he switched to three at the back, with Connor Wickham fit enough to be on the bench after joining the club earlier in the day as a free agent.
Lamouchi was still searching for a first point or goal since becoming the third Cardiff boss of the season at the end of January.
His side produced efforts from Sory Kaba, Cedric Kipre and Ng in the opening 30 minutes, but none found the target, and when Ryan Wintle forced Birmingham goalkeeper John Ruddy into a comfortable save just before the interval, it proved the only first-half effort on target.
And Blues striker Lukas Jutkiewicz's weak header after the break was the first save of the game for Cardiff goalkeeper Ryan Allsop.
Cardiff threatened twice from volleyed efforts by Kaba as they sensed a chance to end their long winless run, before Birmingham's lacklustre display prompted a quadruple substitution from Blues boss Eustace.
Lamouchi waited 73 minutes before introducing Wickham and he was instantly into the action, forcing Ruddy into a rare save.
The contest seemed highly liable to end in a stalemate but Ng had other ideas when he curled home a fabulous freekick after Callum O'Dowda had been fouled.
Wales Under-21 international Jordan James missed a good chance to level for Blues from close range on 89 minutes, but Robinson made the result safe when the former West Brom striker scored on the break, beating Ruddy at his near post after a mazy run.
Birmingham City: Ruddy, Colin, Sanderson, Dean (James 86'), Trusty, Bielik, Mejbri (Hall 72'), Bacuna (Gardner 72'), Chong (Longelo 72'), Jutkiewicz (Deeney 72'), Hogan.
Subs not used: Etheridge, Friend, James.
Cardiff City: Allsop, Romeo (Philogene 73'), Ng, Kipré, McGuinness, O'Dowda, Sawyers, Wintle, Rinomhota (Ralls 86'), Kaba (Wickham 73'), Etete (Robinson 73').
Subs not used: Alnwick, Simpson, Ojo.