Gunners pick up a huge win at the expense of the persistent Magpies and now move to within a point of neighbours Spurs as they search for the final automatic Champions League spot
Hatem Ben Arfa opened the scoring with a venemous strike before Robin van Persie equalised less than a minute later.
Thomas Vermaelen popped up in stoppage to sweep home Theo Walcott's cross and give the Gunners a huge win.
Arsene Wenger made one change from his side's heartbreaking 3-0 win over AC Milan with Mikel Arteta replacing Gervinho.
For Newcastle, Ryan Taylor was forced out with injury and Papiss Cisse was dropped to the bench, Ben Arfa and Gabriel Obertan coming in.
The Magpies took a stunning lead in the 14th minute. Vermaelen gave the ball away cheaply in midfield to Cheick Tiote, the ball was worked to Ben Arfa and the Frenchman cut inside Kieran Gibbs before smashing the ball past Wojciech Szczesny at his near post.
Less than a minute later the Gunners were level. Straight from the kick-off, Tomas Rosicky released Walcott down the right side, the Englishman crossing for Van Persie who turned onto his left foot and slammed the ball past Tim Krul.
The Dutchman went close with a free-kick soon after but the Arsenal skipper's effort flew into his compatriot's arms.
Newcastle were holding their own with a five-man midfield, the pace of Ben Arfa, Gabriel Obertan, Jonas Gutierrez causing problems on the counter attack.
Gutierrez went close after Mike Williamson nodded down Yohan Cabaye's deep free-kick but the Argentine's effort was charged down.
Arsenal had a great chance to take the lead late in the half, a corner from Alex Oxlade-Chamberlain fell to Walcott and the England winger's scuffed effort beat Krul but was hacked off the line by Danny Simpson.
Former Nottingham Forest defender James Perch was brought on at half-time in place of Davide Santon in an attempt to stem the tide of Arsenal's right sided attacks though Walcott and Bacary Sagna.
The Gunners made a good start to the second period, Walcott saw a firm header palmed away by Krul before Oxlade-Chamberlain hit a dipping volley over the bar.
The Magpies were on the ropes as Arteta's volley was blocked before Krul saved smartly from Van Persie's snapshot. Oxlade-Chamberlain was looking lively on the left, flying past two players before showing a lack of composure and firing well wide.
Alan Pardew made a change, bringing on derby hero Shola Ameobi for Obertan who had struggled to impose himself, plying behind the totemic Demba Ba.
Arsenal continued to press, Walcott got the better of Perch down the right and cut the ball back to Rosicky who scuffed his shot well wide, Wenger made a change as he searched for a winner, replacing a visibly disappointed Oxlade-Chamberlain with Gervinho.
The game had become a scrappy affair with Cheick Tiote and Laurent Koscielny going into Howard Webb's notebook and Ba on the end of some rough treatment from the Arsenal players.
Sloppy play in defence almost cost Newcastle as Simpson ad Ben Arfa tried to play their way out of defence, Gibbs nipping the ball away and feeding Van Persie but the Dutchman was unable to capitalise with a wild right-footed effort.
The Gunners were hammering on the door but were unable to find a goal, Arteta fired a free-kick across the six-yard box which fell to Gervinho but the Ivorian was caught off balance and scuffed his effort wide.
Krul was at his very best in the 90th minute. Alex Song's chipped ball in found Vermaelen, the Belgian's looped header looked destined for the net before the Dutchman sprung into life to superbly tip the ball over the bar.
The Gunners still poured forward in stoppage time, a sweeping move fell to Sagna who whipped a fine ball into the path of Walcott who's first-time effort was blocked by Fabricio Coloccini, with Arsenal players claiming handball by the Argentine.
Arsenal finally got their goal in the fifth minute of stoppage time. Theo Walcott lead the charge down the right flank, flying down the wing before sweeping a cross into Vermaelen who smashed home a deserved winner to ensure the Gunners have come form behind to win their last four games, a Premier League record.