Subs Not Used: Krul, Coloccini, Ryan Taylor, LuaLua.
Toon Win 'Demolition Derby'!
Subs Not Used: Krul, Coloccini, Ryan Taylor, LuaLua.
MIDDLESBROUGH: Jones, Hoyte, Bates, Huth, Taylor (Adam Johnson 76), Downing, O'Neil,Shawky (Aliadiere 69), Sanli, Emnes, Alves (King 36).
Subs Not Used: Turnbull, Arca, McMahon, Grounds.
Martins struck within seconds of replacing Michael Owen with 20 minutes of a pulsating encounter remaining and the Dane secured the points with four minutes left to drag the Magpies out of the relegation zone and send Hull into the bottom three.
It was Newcastle's first home win since December 21, the first for Alan Shearer as manager and just their second anywhere in 18 attempts.
Beforehand Shearer had described it as the biggest match of his career, and he celebrated accordingly on the final whistle.
Boro had taken a third-minute lead when the unfortunate Habib Beye bundled the ball into his own net after goalkeeper Steve Harper had blocked Tuncay Sanli's close-range shot.
However, defender Steven Taylor levelled within six with a bullet header after Boro old boy Mark Viduka had hit the post.
Owen, who admitted his disappointment at being dropped for the trip to Liverpool last time out in his programme notes, returned to the starting line-up in one of five changes as Shearer went for broke.
However, with Boro also having reached the point of no return, Southgate too adopted an attacking approach with record signing Afonso Alves partnering Marvin Emnes in attack as the Dutchman was handed a first league start, and Stewart Downing lined up on the right in an attempt to test makeshift full-back Damien Duff.
The first goal arrived within three minutes of the kick-off, but for Shearer, it came at the wrong end and with a good deal of misfortune.
Tuncay turned well on Alves' pass, but looked to have overrun the ball.
He got there just ahead of the fast-advancing Harper, who blocked, only to see the rebound ricochet back off Beye and into his own net.
Newcastle's luck did not improve at all three minutes later when Viduka blasted a shot towards Brad Jones' top corner, but with the goalkeeper looking on helplessly the ball cannoned back off the post.
But if there was any sense of despondency at St James' it disappeared with nine minutes gone when Taylor rose to meet the first of a series of Danny Guthrie corners and guided a header past Jones.
The home side took the game by the scruff of the neck and Jones had to pull off a vital fingertip save to keep out Owen's flicked 27th-minute header.
But Boro gradually eased their way into the game and with Downing and Tuncay prospering on the wings and Emnes causing all kinds of problems to stretch the Magpies defence, they threatened to restore their lead.
They very nearly did just that when the Dutchman benefited from Mohamed Shawky's tackle on Viduka deep inside his own half and blasted in a shot which Harper blocked with his legs, and the striker wastefully dragged the loose ball wide.
Alves later departed on a stretcher to be replaced by Marlon King, but the game was very much in the melting pot as the players headed for the dressing room.
Viduka might have put the home side ahead with the cheekiest of efforts when he back-heeled Beye's 46th-minute cross wide of the far post, and Nicky Butt drilled a free-kick into the defensive wall as the Magpies started brightly once again.
But Boro's response was concerted and as the home side completely lost both their shape and concentration, it took an excellent save from Harper to keep out Gary O'Neil's goal-bound 57th-minute strike.
The Teessiders were by now looking the more likely to break the deadlock, and Shearer decided the time had come to replace Jonas Gutierrez with Lovenkrands.
But it was Martins' arrival as a 70th-minute substitute for Owen which proved the turning point.
Viduka headed on a high ball past Kevin Nolan and the Nigerian stepped inside Matthew Bates before dispatching the ball past Jones despite slipping as he shot.
The noise inside St James' almost lifted the roof, although the game was far from over as the home fans settled down for an agonising finish.
But Lovenkrands calmed the nerves with four minutes remaining when he thumped home Nolan's cross to seal a win as important as any in the club's recent history.