new year at St James' Park with a much-needed three points.
First-half goals from Shola Ameobi and Lee Bowyer were enough to end the Magpies' two-month search for a home win in the Premiership, and in doing so end Birmingham's own four-game winning streak.
The Blues did mount a second-half comeback, with Emile Heskey finding the net midway through the half, but they could not find an equaliser.
United did it without Alan Shearer, whose expected comeback from a six-week lay-off was put on hold due to a fresh injury picked up in training on the eve of the game.
Souness had kept faith with the team narrowly beaten by Premiership champions Arsenal in midweek, while Steve Bruce made one change from the side that beat Fulham with Stan Lazaridis starting in place of Jamie Clapham.
And Souness' team, looking for their first home league win since October 24, got off to the ideal start when they took a sixth minute lead.
Craig Bellamy, playing wide right for the second game in a row, beat Olivier Tebily on the left and crossed for lone striker Ameobi, who beat Kenny Cunningham to the ball to head home past Maik Taylor from close range for his first Premiership goal of the campaign.
Birmingham remained on the back foot in the early stages, with Ameobi going close again and Bowyer then forcing a save from Taylor.
Laurent Robert then set Bowyer away through the middle in the 21st minute, but again he was denied by Taylor.
Bruce replaced Tebily with Julian Gray in the 25th minute, with the defender having been given a torrid time by Bellamy in the opening stages.
Lazaridis dropped back to left back, with Gray lining up on the wing. Newcastle continued to press in the pouring rain, and added to their lead just before the break.
Robert took the ball off one-time United target Mario Melchiot on the left wing and crossed for Bowyer, arriving late and unmarked in the box, and the former Leeds United midfielder drilled a low shot to the left of a helpless Taylor.
Bruce resisted the temptation to make further changes at half-time, and by the time both teams ran out for the second half the torrential rain which had plagued the first half had abated.
But the pitch was already heavy, and there were some tired legs. Souness replaced Robert with James Milner, and Bruce brought on Darren Anderton for
Darren Carter.
And seconds after Anderton's introduction in the 64th minute, the ball was in the back of the net.
Clinton Morrison took the ball with his back to goal, and played in his unmarked strike-partner Heskey. The ex-Liverpool forward raced into the box and lashed a fierce left-foot shot past Shay Given at his near post.
An injured Bellamy was replaced by Charles N'Zogbia in the 76th minute, with Milner pushed up alongside Ameobi for the final stages.
Bruce threw on striker Dwight Yorke for the final few minutes in place of defender Cunningham, but the Blues' three-man strikeforce could not fashion an equaliser.
MAN OF THE MATCH: Titus Bramble (Newcastle United) - Widely tipped to be leaving Tyneside following the arrival of Boumsong, the former Ipswich man produced one of his best displays in a Newcastle shirt.