Obafemi Martins' seventh goal of the season from the penalty spot, his sixth in the league, had earlier wiped out an early Cameron Jerome goal as Alex McLeish tasted defeat for the first time as Birmingham boss.
In front of their lowest home league crowd of the season, 49,948, the win greatly eases the pressure on Sam Allardyce whose side have now claimed five points from a possible 21.
Fresh from their greatly improved performance against Arsenal, Allardyce not surprisingly named an unchanged Newcastle side.
But just as they had done against the Gunners, United found themselves behind to an early goal following yet another defensive error after nine minute.
This time David Rozehnal was the culprit when the Czech international failed to allow for the conditions in the torrential rain and Cameron Jerome capitalised by stealing possession before cleverly rounding Shay Given and placing his shot into the empty net.
This was the 12th successive game that Newcastle had failed to keep a clean sheet, but on the credit side they refused to allow their heads to drop and laid siege on the Birmingham goal for the remainder of the first half.
Maik Taylor knew little about keeping out a point-blank save from Martins and Rafael Schmitz cleared off the line.
United lost Nicky Butt with a groin strain on the half-hour mark and he was replaced by Mark Viduka, who made an immediate impact with his physical presence.
The equaliser came from the penalty spot after 35 minutes when referee Rob Styles was perfectly positioned to see the trailing leg of Matthew Sadler send Martins crashing to his knees.
He awarded what was the first penalty of the season involving Newcastle and Martins climbed off the floor to take the kick.
Quite adept at taking penalties with either foot, Martins shaped to take left-footed, but switched in his run-up and saw Taylor get both hands to the ball, but frustratingly for the Northern Ireland number one saw the ball hit the upright and went over the line.
James Milner then twice within the space of a minute should have put Newcastle ahead after 40 minutes.
England's record Under-21s appearance maker got on the end of a Charles N'Zogbia free-kick only to see Taylor turn it over the bar and from a free-kick smashed a 20-yarder against the woodwork.
Despite finishing the half on a high, United then allowed the Blues to take the early second period initiative and it should have seen them regain the lead when Sebastian Larsson - the matchwinner at Spurs last week - blasted wide when he should have done better.
Play deteriorated along with the weather until Allardyce sent on Emre for the once again disappointing Geremi.
And Emre was to have two important parts to play in a grandstand finish. First he appealed for a second penalty when a late free-kick struck the outstretched arm of Jerome.
Then with a last throw of the dice United snatched their first win since beating Spurs on 22 October. Emre's near-post corner was met by the flying Beye, whose downward header flashed into the net.