Strikes from Shola Ameobi and Jermaine Jenas, and an own goal from Gerry Taggart, saw the Magpies take a lead from which the Foxes were unable to recover, although one-time United striker Les Ferdinand scored a consolation for City.
Newcastle were far from their scintillating best, but they did not have to be to beat a poor Leicester team at St James' Park.
Sir Bobby Robson had made two changes for the visit of Leicester, with Ameobi coming in for Darren Ambrose and Hugo Viana taking the place of the injured Laurent Robert.
Micky Adams, meanwhile, made four changes from the 5-0 home defeat to Aston Villa, among those missing out being Nikos Dabizas due to a clause in an agreement struck between the two clubs when the Greek star quit United for City.
Another former Magpies defender was remembered before the game, with St James' observing a minute's silence for Bob Stokoe who died last week.
Steve Guppy, who also once wore the black and white of Newcastle, created the first real chance of the game when his throughball opened the home side up but Shay Given raced off his line to beat Paul Dickov to the ball in the eighth minute.
Seconds later Callum Davidson shot wide from distance as Leicester's bright start continued against Robson's Champions League-chasing team.
But United, beaten just twice in their previous 17 Premiership games but with an unenviable record for drawing games, soon perked up and Gary Speed and Olivier Bernard had shots blocked as Robson's men pressed the visiting defence.
In the 23rd minute it was the unlikely figure of right back Aaron Hughes who fired in a shot at Ian Walker's goal but again this was deflected.
No sooner had that corner been cleared, Newcastle had another as United attempted to find an opening and in their fourth corner of the half Ameobi headed narrowly wide from Viana's centre with 24 minutes on the clock.
Then Kieron Dyer, dropped back into midfield for the game following a spell as strike partner to Alan Shearer, forced a superb save from Walker, with the Foxes goalkeeper tipping the 20-yard effort away to safety.
And as it turned out Newcastle's breakthrough was not long in coming, with Ameobi marking his return to the side with a 29th minute goal.
Andy Impey's misjudged clearance dropped in front of the England Under-21 forward and Ameobi squeezed the ball between Walker and his right-hand post.
It was Ameobi's fourth Premiership goal of the season and it was Shearer, looking for his 300th career goal on the afternoon Gary Speed made his 400th Premiership appearance, who had forced Impey's error.
And United forced another mistake six minutes later when Bernard's cross from the left was put into his own goal by Taggart, with Shearer having only narrowly failed to connect with the Frenchman's ball.
It hit Walker's crossbar, and although the Foxes claimed the ball had not crossed the line, referee Steve Dunn finally awarded the goal.
But upon his delayed reaction St James' erupted for the second time, and seconds later the heavens opened onto an already muddy pitch.
Leicester, stung by the two goals, tried to respond but Newcastle took their advantage into the half-time interval following 45 minutes of far from classic football on a gloomy Tyneside.
Ben Thatcher was booked shortly before the whistle for a foul on Dyer.
The rain and snow had eased by the re-start as United had yet another corner, this one dealt comfortably with by the visitors.
Ameobi headed wide eight minutes into the half from makeshift winger Viana's left-wing cross as the game lulled, with the 2,000 travelling fans attempting to lift their relegation-threatened team.
Newcastle's football continued to have the greater purpose and the flow of corners ended with another Ameobi shot being deflected wide.
In the 57th minute Dyer raced onto Ameobi's header but the England international was muscled out by Taggart on the edge of the box.
And it was another England midfielder, Jenas, who made it three when he headed Shearer's hooked cross past Walker with 59 minutes gone.
That saw Adams send out three players to warm up, among them former United striker Ferdinand and he got an ovation from the Toon Army having almost fired Newcastle to the Premiership title under Kevin Keegan in the mid-1990s.
But it was Frank Sinclair who first made it on, replacing Andy Impey on an afternoon Adams would already having been wanting to end.
Adams had to wait to bring Ferdinand on as the Foxes supporters in the top tier at St James' chanted: "We're going to win 4-3", like Manchester City in midweek.
Ferdinand, with eight goals to his name this season for struggling Leicester, made it on in the 65th minute and was promptly booed on his first touch, having been cheered onto the pitch by both sets of fans.
It was then fit again Craig Bellamy and on loan Michael Bridges' chance to warm up, with Sir Bobby contemplating bringing even more firepower to bear on the visitors.
But midfielder Darren Ambrose beat Bellamy and Bridges to it, replacing the apparently injured Dyer on the right side of midfield while Jordan Stewart replaced the ineffective Guppy on City's left flank in the 73rd minute.
Good battling from Jenas almost saw Shearer find the target before United's skipper was replaced by debutant Bridges while Bellamy came on for Ameobi in the 79th minute.
But within seconds the ball was in Newcastle's net after Ferdinand buried Jordan Stewart's left-wing cross at the Gallowgate end, something which he had done plenty of times during his two successful years on Tyneside.
United then twice went close, with Bridges first fluffing a shot before Bellamy put another wide of Walker's left-hand post.
Man of the match: Alan Shearer - The veteran striker may not have scored but he had a hand in all three Newcastle goals.