Daniel Cousin's late winner ensured Hull will welcome Millwall to the KC Stadium in the FA Cup fourth round.
A strong-looking Newcastle team started brightly and Xisco scooped the ball over from just six yards out while Nicky Butt's header hit the bar.
But the hosts became nervy and a largely second-string Hull broke the deadlock when unmarked Cousin tucked in from eight yards in the 82nd minute.
Michael Owen then had a chance to equalise but sent a wild header over.
That was just one of three gilt-edged opportunities passed up by the England striker on a hugely disappointing night for Newcastle who, judging by manager Joe Kinnear's team selection, clearly wanted to progress in this competition.
Hull achieving victory in this third-round replay without eight of boss Phil Brown's first-choice players will also rub salt into the wounds on a night when he and Kinnear were sent to the stands by referee Phil Dowd for clashing on the touchline.
606: DEBATEWatched by a crowd of 31,380, the Magpies enjoyed the better of the first half.
They went close to a 21st-minute opener when Butt headed Danny Guthrie's free-kick against the crossbar with goalkeeper Matt Duke beaten.
Both managers were then sent to the stands by Dowd following an angry exchange of views in the wake of Fabricio Coloccini's late challenge on Cousin.
And Newcastle were handed a glorious opportunity 11 minutes before the break, as Hull defenders Paul McShane and Kamil Zayatte ran into each other as they attempted to collect a loose ball.
But Owen, one-on-one with Duke, blasted his effort high over the bar.
Within two minutes of the restart, Owen's low shot was turned round the post by Duke after the forward beat the offside trap to run on to Damien Duff's clever pass over the top.
Hull skipper George Boateng was carried off in the 67th minute after a crunching block tackle by Butt, with Ian Ashbee taking his place.
With 20 minutes remaining Charles N'Zogbia embarked upon a mazy run to the edge of the Hull box, but his shot was well blocked by Zayatte.
But the deadlock was broken when Cousin, with plenty of time and space, turned in Richard Garcia's cross.
Newcastle's Kazenga LuaLua drove across the face of goal late on but it raced too far ahead of fellow substitute Andy Carroll before Owen failed to send the tie into extra-time only to head over another Guthrie cross.
The final whistle then brought a chorus of boos from the stands as Newcastle's season took another turn for the worse.
Newcastle boss Joe Kinnear:
"Hugely frustrating but I can't criticise the players, we had 11 missing. I really should be sitting here talking about us winning by four clear goals.
"They had a smash-and-grab at the end. Here we are out of the FA Cup and bitterly disappointed, but not with the performance.
"Phil Brown and I just exchanged words. He instigated it and I answered him back. But we will have to wait and see what the referee's explanation is."
Hull manager Phil Brown:
"It was all about the result and not the performance, and we got the result.
"People said that with eight changes you've gone and thrown the chance to play Millwall at home. But we don't set out to lose games.
"The lads have restored a bit of belief in the camp with regards to winning games at this level. We've kept a clean sheet against them and gone on to deservedly win."
Newcastle: Given, Edgar, Bassong, Coloccini, N'Zogbia, Gutierrez (LuaLua 82), Butt, Guthrie, Duff, Owen, Xisco (Carroll 76).
Subs Not Used: Harper, Taylor, Kadar, Donaldson, Ranger.
Booked: Coloccini.
Hull: Duke, Doyle, McShane, Zayatte, Ricketts, Fagan (Mendy 74), Halmosi, Boateng (Ashbee 67), France, Garcia, Cousin (Folan 86).
Subs Not Used: Warner, Featherstone, Giannakopoulos, Atkinson.
Booked: Ricketts, Fagan.
Goals: Cousin 81.
Att: 31,380
Ref: Phil Dowd (Staffordshire)
BBC Sport Player Rater man of the match: Newcastle's Shay Given - 7.45 (on 90 minutes).
Please note that you can still give the players marks out of 10 on BBC Sport's Player Rater after the match has finished.
Player Rater~RS~q~RS~~RS~z~RS~02~RS~)