However, United needed to win by three clear goals to not only overhaul Charlton, but also Liverpool for that fourth spot which the Reds currently hold down by virtue of having scored more goals than Sir Bobby Robson's men.
Two Alan Shearer strikes - one in each half - and another from Jermaine Jenas did the trick, with Claus Jensen replying for Charlton who now find themselves two points behind Newcastle in sixth place.
And the outstanding Shearer believes the points went to the best side, claiming: "We fully deserved it.
"This was a big win for us with Charlton above us and with Liverpool winning in the afternoon. Our first-half display was very good but it was impossible to keep up that level of performance for 90 minutes.
"Charlton came more into in the second half and but for a world class save from Shay Given it could have been a different result."United got off to a dream start with a goal after just 57 seconds from the inspirational Shearer.
Laurent Robert did the spadework when a long throw on the left was headed back to him. The Frenchman looked up and curled in the most delightful of crosses and Shearer forced his way in front of Hermann Hreidarsson to head past Dean Keily at the near post for his 239th Premiership goal.
The shell-shocked Addicks were all over the place as rampaging Newcastle ran the early part of the show.
Indeed it could easily have been two after just three minutes when a right wing corner from Darren Ambrose saw Gary Speed left unchallenged, but from 12 yards the Wales skipper headed over.
With four defeats from their last six Premiership away matches, Charlton had no answer to United, who dominated the centre of the park where Jenas was particularly impressive with his powerful running and non-stop approach to the game.
Kiely was called into action after 13 minutes when Robert - searching for his 13th goal of the season - drilled in a 25-yard free-kick that saw the keeper claw the ball behind for a corner.
Charlton managed their first and only attempt of the first half after 23 minutes, but the acute effort from Radostin Kishishev ended up in the side-netting.
Shola Ameobi - in for the injured Craig Bellamy - showed his exceptional skills soon afterwards when he caused problems on the left and drilled the ball across the area, but unfortunately just behind Speed.
Ameobi then showed his heading prowess after 28 minutes when meeting a left-wing cross from Olivier Bernard but, although he got in front of Jonathan Fortune, he could not keep his header down.
Shearer who was on the wrong on of some strong tackles was floored yet again on the half-hour and Chris Perry - just back from a one-match suspension - was shown a yellow card.
The second goal that United deserved for their outstanding opening half display arrived after 35 minutes.
Shearer's headed flick-on was won by Ameobi who wriggled his way into the area before the ball ricocheted across the box, only for Luke Young to blast his clearance against Jenas and into the net.
United lost the injured Aaron Hughes who failed to appear for the second half and was replaced by Titus Bramble, who quickly found himself up against it as revitalised Charlton took the match to Newcastle.
The third goal was always going to be crucial and it went the way of Alan Curbishley's men after 54 minutes. Paul Konchesky did the damage on the left and when his cross was not reached by Bramble, Claus Jensen was first to react and swept the ball beyond Given.
It was a goal that would ultimately have a big bearing on United's league position at the end of the evening.
It was then a case of backs-to-the-wall for United as the Addicks pressed forward at every opportunity and there was plenty of panicking in the United rearguard.
Yet it was Newcastle who should have regained their two-goal advantage on 66 minutes but were let down by a glaring miss from Ameobi.
It was route-one stuff with Shearer heading a Given kick straight into the path of the England Under-21 striker who, just 12 yards from goal, snatched at the ball and fired woefully wide.
The warning signs were there for United after 72 minutes when the industrious Jensen picked out Carlton Cole with a slide-rule pass on the right of the area and the youngster drove hard across the goal, leaving Given delighted to hang onto the ball with Paulo Di Canio closing in.
The Newcastle goal had a charmed life just three minutes later when the Addicks were denied an equaliser by a world class save from Given.
With United organising their defence Di Canio took a quick corner on the right which found Chris Perry, whose first-time volley flew through the crowded goalmouth only for the unsighted Given to pull off a wonderful reflex save.
Within sixty seconds Perry turned from potential hero to villain when United grabbed the goal that settled issue and secured those vital three points.
A lightning quick raid saw Darren Ambrose escape on the right and play the ball into the path of Robert who cut into the area and went sprawling over the outstretch leg of former Spurs defender Perry.
Referee Mike Riley had no qualms about pointing to the spot, with the Charlton players justifiably claiming that the Frenchman had dived.
As ever Shearer remained the calmest man on the pitch as he placed the ball on the spot.
The Magpies skipper shot to the right of Kiely, who guessed correctly and touched the ball onto the post, only to see it shoot back across the goal where Shearer was first to react, making absolutely no mistake in tapping the ball in.
Still Charlton were not finished and substitute Jonatan Johansson hit the United post, as a relived Newcastle made it seven successive wins at St. James' Park.
MAN OF THE MATCH - ALAN SHEARERCaptain fantastic produced a stunning individual display and another two goals to take his Premiership haul to 240 from his spells with United, Blackburn and Southampton. He led by example and showed what a miss he will be when he retires at the end of next season.