Back from injury, skipper Alan Shearer fired United in front with an early penalty and big defender Titus Bramble made it 2-0 before Peter Crouch pulled one back late in the first half.
It should have been done and dusted for Newcastle well before the break but their inability to put away chances could easily have led to their downfall.
Overall it was the right result, though the gallant Saints did stage a late revival and could easily have pinched a point.
After an absence of 12 games Captain Fantastic was finally back in action. Despite Graeme Souness stating 24-hours earlier that master marksman Shearer would be on the bench, the Scot pulled off a major shock by naming the former Saints hitman in the starting line-up.
Souness made a total of three changes to the side that won 2-0 at Loftus Road against non-league Yeading in the third round of the FA Cup, with Kieron Dyer and Shay Given also back in the starting line-up.
The Magpies also handed Premiership debuts to new signings Jean Alain Boumsong and Celestine Babayaro.
Worryingly for Newcastle, bogey official Uriah Rennie was in charge of the match. In their previous nine Premiership matches handled by Rennie, United had lost eight times and won just the once – a 1999 win at Leeds courtesy of a solitary goal from Nobby Solano.
United were awarded a penalty just into the fifth minute when Calum Davenport pulled Shola Ameobi as he went for a ball over the top from Bramble. Antti Niemi was injured in the collision with the United striker and after considerable treatment was carried off and replaced by Paul Smith.
After four minutes Shearer eventually stepped forward and fired to Smith's left with the keeper diving the other way, and his first touch was to pick the ball out of the net.
United then strung a superb move together that ended with Bellamy picking out Ameobi who skipped around Davenport only to see his shot blocked, and just afterwards the industrious Lee Bowyer drove over from 20 yards.
Saints finally managed their first effort on target after 20 minutes, but Crouch's looping header posed no problem for Given.
Play switched straight to the other end and Bellamy came in from the left to be denied by legs of Smith, before Shearer linked well with youngster Steven Taylor who broke into the box and set up Ameobi who scuffed a shot at Smith.
The overworked Saints defence was carved wide open again after 25 minutes and it took a flying save to his left from Smith to deny Jermaine Jenas from 20 yards.
United were denied a clear-cut penalty two minutes later when Davenport – on loan from Spurs - again fouled Ameobi, but Rennie refused a second spot kick.
Dominant in midfield, United were running the show and Dyer was allowed to break forward and saw his side-footer drift only inches wide.
The Southampton goal then had a great escape after 36 minutes when Bellamy cut in and picked out Jenas, whose goalbound effort cannoned of team-mate Boumsong to safety.
There then followed a nightmare 60 seconds for Southampton in the 37th minute. Crouch and Paul Telfer were both booked for fouls on Taylor and Bellamy respectively.
The second free-kick was swing in by Babayaro from the left and Bramble lost his marker and side-footed home.
In cruise control, United let it slip three minutes from the break. David Prutton worked a short corner with McCann and his deep cross was nodded back by Davenport only for Kevin Phillips to head against the bar - but Crouch fired the rebound through Given's legs to make it 2-1.
Smith then came to Saints' rescue again deny a top corner bound effort from Bellamy.
The Welshman was presented with a good early second half opportunity by Shearer, but missed the ball completely before volleying over from a great position three minutes later.
On the hour mark, United won four successive corners as the piled on the pressure before Shearer received a standing ovation when he was replaced, by Patrick Kluivert.
Smith had to be alert after 76 minutes when an Ameobi shot struck a divot as he was diving and just managed to touch it behind for a corner. Substitute James Milner then saw the flag kick returned to him and Smith did well to keep out his low angled drive.
Another substitute popped up at the other end and Anders Svensson should have done better than headed over from Crouch's centre.
With the game in the dying seconds Telfer had a low drive saved by Given, before Taylor produced a last-gasp block to stop Prutton grabbing an equaliser.
Man of the Match Steven Taylor
The youngest member of the Newcastle team continues to improve with every game. His physical power and dynamic approach has proved to be a breath of fresh air for Newcastle.