Danny Webber scored Sheffield United's first Premiership away goal of the season as the Blades leapfrogged Newcastle and out of the bottom three.
Webber's winner could be vital in the relegation shake-up
Webber stooped to head home Nick Montgomery's cross to inflict the Magpies' third home League defeat.
Blades' keeper Paddy Kenny's only concern came when Charles N'Zogbia's first-half cross dropped on to the bar.
But Newcastle failed to trouble the Blades' solid defence and were booed off by a frustrated home crowd.
The Blades had an early chance to notch their first away Premiership goal when Webber broke clear down the right but Stephen Carr just did enough to smuggle the ball away from Rob Hulse when the cross came in.
Titus Bramble, who had ventured forward to plant a free header yards wide from Damien Duff's corner, then lost the flight of Kenny's long punt allowing Hulse to collect and test Steve Harper with a sharp shot on the spin.
It was a nervous Newcastle in the opening stages, and with their lightweight attack failing to make the ball stick under the physical pressure from Blades' hefty defenders, they found the ball constantly coming back at them.
Newcastle found width through James Milner and N'Zogbia to provide a plentiful supply of crosses but the strike partnership of Giuseppe Rossi and Duff never offered an aerial threat to Claude Davis and Phil Jagielka.
Blades Jagielka and Montgomery gang up on Newcastle's Giuseppe Rossi
Sheffield United created their own problems, with Kenny bailed out by Jagielka after he dropped a corner, and sloppy marking allowing Scott Parker space to volley over.
Kenny was almost embarrassed when he let N'Zogbia's intended cross drift over him on to the crossbar and Newcastle must have been praying for Alan Shearer to come out of retirement to attack some of the inviting crosses that went begging.
It was almost half time before Kenny was stirred into action, but even then Scott Parker's snap shot was a comfy gather for the Blades keeper who had not been seriously tested.
Newcastle boss Glenn Roeder replaced N'Zogbia and Butt at half time with Emre and Nolberto Solano but Craig Moore was lucky to stay on the pitch when he flattened Hulse off the ball, unseen by referee Steve Bennett only yards away.
Despite the substitutions, the pattern remained the same, with Newcastle lacking the physical strength to break down a solid barrier.
Sheffield United offered the threat, with Montgomery drawing a fine save from Harper and Mikele Leigertwood rasping a shot just over.
It was no surprise when the Blades took the lead, when Montgomery was allowed to travel a long distance with the ball before dropping a cross on to Webber's head eight yards out.
Newcastle's efforts to save the game became increasingly ragged and Alan Quinn almost doubled the Magpies' embarrassment when he broke clear and struck the post with his shot.
Newcastle manager Glenn Roeder:
"It was the poorest performance since I've been back involved with the first team. We can't have any more like that.
"I can understand the fans being disappointed as we didn't perform anywhere near the level we can.
"It is very difficult to take any positives out of the whole of the 90 minutes of that match."
Sheffield United boss Neil Warnock:
"It was a very professional away performance. And never mind it being our first away win, it was our first away goal. I am delighted.
"We seemed quite content for it to be 0-0 at half-time. I told the lads that if we improve 20-30% then we could win.
"We did that in the second half and I thought we thoroughly deserved to win."
Newcastle: Harper, Carr, Moore, Bramble, Babayaro, Milner (Luque 66), Parker, Butt (Emre 46), N'Zogbia (Solano 46), Rossi, Duff.
Subs Not Used: Srnicek, Ramage. Booked: Carr, Babayaro.
Sheff Utd: Kenny, Kozluk, Davis, Jagielka, Geary, Montgomery, Leigertwood, Alan Quinn (Law 90), Gillespie, Hulse, Webber (Kabba 72), Kabba (Kazim-Richards 88).
Subs Not Used: Bennett, Short.
Booked: Davis, Hulse.
Goals: Webber 68.
Referee: S Bennett (Kent).