A stunning first-half strike in stoppage time from skipper Patrick Vieira kept Arsenal in the hunt for their quest for back-to-back titles.
The Gunners showed the resilient side of their play as for long spells they found themselves on the back foot against the hard-working Magpies.
United went into the match without a win in their last seven clashes with the Gunners, who were rated as odds-on favourites by the bookies with Newcastle quoted at just 3/1 to topple the champions.
With just one win in their last nine Premiership matches, United were given a boost when Kieron Dyer declared himself fit for Graeme Souness' injury-ravaged side.
Olivier Bernard returned to the defence with a question-mark hanging over his Newcastle career following the speculation that Celestine Babyaro - who met with chairman Freddie Shepherd on Tuesday - is set to sign for United during next month's transfer window.
After some good early possession United went close to going a goal behind in the fourth minute as Arsenal won three successive corners.
The Newcastle defence was caught ball-watching when Robin Van Persie ghosted in from the right on the blind side to strike a first-time shot that cannoned behind off the head of the unaware Shay Given for the first of those flag kicks.
Arsenal played some attractive football before Shola Ameobi muscled Sol Campbell off the ball on the edge of the box to get in a shot that appeared to be deflected behind although a goal kick was given much to the dismay of the home fans.
Ameobi came to Newcastle's rescue with a crucial headed clearance off the line on the quarter-hour mark to deny Campbell's header from a corner.
Ameobi then broke free of the Arsenal defence but his pull-back evaded the United strikers and then Dyer just failed to make contact with an Ameobi knockdown with the goal at his mercy.
Steven Taylor picked up the first yellow card after 33 minutes for a foul - ironically only United's fourth foul of the half - on Robert Pires and seconds later Campbell headed a Van Persie corner over the bar.
Van Persie tested Given with a 30-yarder that was turned away for a corner before United's players protested furiously when they were not awarded a 39th minute penalty. Ashley Cole clearly punched a left-wing cross inside the box right under the nose of referee Bennett.
Persistent fouling saw Cole booked just before the break as Newcastle enjoyed their most successful attacking period.
Then completely out of the blue - ten seconds from the end of the one minute added on for stoppages - Vieira scored a great goal out of nothing to stun the home crowd.
The ball was bobbling around on the right when, from 23 yards, the French international tried his luck and thumped a stunning cross-shot that took a slight defection off Jermaine Jenas and over the despairing Given.
Good work from Titus Bramble and Craig Bellamy presented Lee Bowyer with an early second-half chance that he hit well over from just inside the box.
Dyer then forced Manuel Almunia to go full length to save as United strove for the equaliser they deserved for their attacking approach.
Laurent Robert had a free-kick cleared by the awesome Campbell as Newcastle's approach work only lacked the necessary finish.
Arsenal continued to look dangerous on the break with Thierry Henry twice trying efforts from outside the area - the second going narrowly wide - but the visitors had already done enough to clinch another three points on Tyneside.