Match ends, West Ham United 2, Newcastle United 3.
Newcastle United manager Steve Bruce says it would be "nice" to receive the same support as predecessor Rafael Benitez after celebrating an important Premier League win with the travelling supporters.
Newcastle's goalscoring woes disappeared as they found their cutting edge to ease past a woeful West Ham and move four points clear of the relegation zone.
Bruce, who has still not won over the supporters sceptical about his appointment as Benitez's successor, believes his team's first-half performance in east London was their "best 45 minutes" since he arrived in the summer.
Newcastle had scored once in their previous five games and led when Ciaran Clark lost his marker from a free-kick to head in the opener.
The visitors doubled their lead from another set-piece when Federico Fernandez outjumped Hammers goalkeeper Roberto, who wandered off his line, to head into the empty net.
Newcastle had plenty more chances to extend their lead, finally grabbing a third when Jonjo Shelvey clipped in a precise free-kick after half-time.
West Ham pulled one back when Fabian Balbuena bundled in from close range and set up a grandstand finish through Robert Snodgrass's neat effort in injury time.
But a dramatic equaliser would have been unfair on Newcastle, who hung on to spark wild celebrations in the away end at the full-time whistle.
"It could have been slightly better and a little more easier, the first half in particular was the best we've played since I've been at the club," Bruce told BBC Match of the Day.
"We looked rock solid and on the counter we looked very dangerous, but if we're going to be ultra critical we have to take the chances we got and if we had taken them we would have got four or five."
On the response of the travelling fans at the final whistle, he added: "I'm going to try and enjoy it and hopefully in time, with results, they will get behind me as much as they did Rafa. That would be nice."
- Relive how Newcastle ended their scoring woes at West Ham
- Catch up on all of Saturday's Premier League action
Newcastle front three offer signs of hope for Bruce
Newcastle's problems have been laid bare over the first three months of the season, with supporters given little to cheer about by a toothless attack that had not scored more than once in any of their opening 10 Premier League games.
That all changed in an almost-perfect away day for the Toon Army.
Bruce's side were organised defensively and rarely threatened until the Hammers' late fightback, while clinically punishing their opponents at the other end.
Even though the opening two goals came from set-pieces, Newcastle constantly caused panic in the home defence through their pacy counter-attacking and should have enjoyed a greater margin of victory at London Stadium.
French youngster Allan Saint-Maximin was a particular nuisance throughout, causing veteran Hammers full-back Pablo Zabaleta all sorts of problems with his speed and trickery.
Saint-Maximin, 22, started to stretch the home defence and twice could have extended the lead when he sprinted through on goal only to be denied by Hammers keeper Roberto on both occasions.
Brazilian striker Joelinton has been criticised for a lack of goals since his £40m move from German club Hoffenheim but teed up Clark's opener with an unselfish header back across goal from Shelvey's free-kick and worked hard throughout.
Paraguayan winger Miguel Almiron was also lively for the visitors, only to be again let down by his end product and spurning a chance late on to score a fourth and ease the pressure.
"They are all young lads at the top of the pitch and they need time to settle in and bed in," Bruce said.
"We've paid a lot of money for them and those price tags bear on them. It's a glimpse of what we can do and I was delighted with some of our forward play."
West Ham need a 'reality check' after poor display
While the celebrating away end remained packed immediately after the final whistle, hordes of West Ham fans had already long left London Stadium in disappointment.
After a promising start to the season the Hammers have slid down the table after five league matches without a win and are now only a point clear of Newcastle in 13th place.
Manuel Pellegrini's side appear to have still not recovered from the scars of that humiliating League Cup defeat by League One side Oxford United which has proved to be the catalyst for this dismal run.
The Hammers lacked ideas in the final third of the pitch, unable to create any clear-cut chances from open play in a first half dominated by Newcastle.
The home fans began to show their frustration, notably after keeper Roberto should have stopped Shelvey's free-kick from creeping in, and had already left in their droves before Balbuena and Snodgrass sparked a fightback which had looked unlikely over the previous 70 minutes.
Ultimately it came far too late and produced a final scoreline which did not truly reflect Newcastle's superiority.
"It's a bad result and it is a performance that isn't West Ham like," Hammers scorer Snodgrass told BBC Match of the Day.
"We need a reality check and need to know we need to start getting points on the board.
"We need to be solid and resolute, we could have been four or five down. We can't give teams a three goals start."
Man of the match - Allan Saint-Maximin (Newcastle)
France Under-21 international Saint-Maximin was a nuisance throughout for West Ham but was unable to cap his display with a goal, despite having a game-high three shots on target.
"He should have scored but you can see he is a handful and will get people off his backsides," Magpies boss Steve Bruce said.
"He's that little bit of different. He is exciting and quick and if he can learn to be more clinical we will have a player on our hands."
'I don't understand why we played so bad' - post-match reaction
West Ham manager Manuel Pellegrini: "It is really difficult to explain why we played the way we did in the first 45 minutes.
"The last two games we played at home we started by pressing from the beginning, playing in the opposite half.
"I do not understand why we played so, so bad."
Why Newcastle enjoy their trips to London - the stats
- West Ham are now without a win in five Premier League games, their longest winless streak in the competition since a run of eight ending in December 2017
- Newcastle have scored more than once in a Premier League game for the first time this season, becoming the last side in the top flight to hit two or more goals in a match in the competition this season
- West Ham boss Manuel Pellegrini suffered his first defeat in his ninth Premier League meeting with Newcastle
- Newcastle have tasted victory on three of their last four Premier League visits to London, as many wins as they managed in their previous 24 trips to the capital in the division
- Newcastle have scored two headed goals in the first half of a Premier League game for the first time since December 2006 against Tottenham
- Five of Newcastle's Premier League goals this season have come via defenders this season, more than any other side
- Jonjo Shelvey netted his first direct free-kick goal in the Premier League with his 31st attempt
- Robert Snodgrass has scored in consecutive Premier League games after going 21 such appearances without a goal going back to December 2018
West Ham look to halt their slide when they go to Burnley on Saturday, 9 November at 15:00 GMT, while Newcastle hope to take this form to St James' Park when they host Bournemouth at the same time.
- 5ZabaletaSubstituted forFredericksat 72'minutes
- 23DiopBooked at 14mins
- 3CresswellBooked at 49mins
- 7YarmolenkoSubstituted forLanziniat 45'minutes
- 16NobleSubstituted forAjetiat 45'minutes
- 8Felipe Anderson
- 15C Sánchez
- 18FernandezBooked at 90mins
- 15WillemsSubstituted forDummettat 87'minutes
- 10Saint-MaximinSubstituted forAtsuat 77'minutes
- 9JoelintonSubstituted forCarrollat 89'minutes
- 43M Longstaff
- Stuart Attwell
- Shots on Target
Second Half ends, West Ham United 2, Newcastle United 3.
Federico Fernández (Newcastle United) is shown the yellow card.
Goal! West Ham United 2, Newcastle United 3. Robert Snodgrass (West Ham United) left footed shot from the centre of the box to the bottom right corner. Assisted by Manuel Lanzini.
Substitution, Newcastle United. Andy Carroll replaces Joelinton.
Substitution, Newcastle United. Paul Dummett replaces Jetro Willems.
Foul by Ryan Fredericks (West Ham United).
Christian Atsu (Newcastle United) wins a free kick on the left wing.
Attempt saved. Manuel Lanzini (West Ham United) right footed shot from outside the box is saved in the centre of the goal.
Attempt saved. Miguel Almirón (Newcastle United) left footed shot from a difficult angle on the left is saved in the bottom right corner. Assisted by Ciaran Clark.
Attempt missed. Joelinton (Newcastle United) right footed shot from outside the box is just a bit too high.
Attempt missed. Miguel Almirón (Newcastle United) right footed shot from the right side of the box is high and wide to the right following a fast break.
Substitution, Newcastle United. Christian Atsu replaces Allan Saint-Maximin.
Goal! West Ham United 1, Newcastle United 3. Fabián Balbuena (West Ham United) right footed shot from very close range to the bottom right corner following a corner.
Attempt saved. Sébastien Haller (West Ham United) header from the left side of the six yard box is saved in the bottom right corner. Assisted by Felipe Anderson with a cross.
Corner, West Ham United. Conceded by Federico Fernández.
Substitution, West Ham United. Ryan Fredericks replaces Pablo Zabaleta.
Attempt missed. Declan Rice (West Ham United) right footed shot from outside the box is too high. Assisted by Sébastien Haller.
Aaron Cresswell (West Ham United) wins a free kick in the defensive half.
Foul by DeAndre Yedlin (Newcastle United).