By Dan King
The duo combined to set up United's first for Nolan, then Carroll grabbed his fifth of the season with what turned out to be the winner to see Chris Hughton's men rise from 16th before play began to ninth place in the Barclays Premier League come Saturday evening.
But while the Newcastle number nine and his erstwhile captain will be the biggest news, this was a real team performance full of character, passion and skill.
After a shakey first quarter of an hour where they were perhaps fortunate to be only one goal down, The Magpies regrouped and set about outplaying their hosts for the rest of the game. In the end, Newcastle looked like the home side, zipping the ball about as The Hammers chased shadows.
Chris Hughton had promised his team would be positive. They were certainly that. Hughton made three changes from the team which salvaged a late point at home to Wigan the previous weekend, handing Danny Simpson a first start since his ankle operation in the summer, recalling Kevin Nolan who missed the Latics encounter with a knock and starting Shola Ameobi alongside Andy Carroll. James Perch, Danny Guthrie and Peter Lovenkrands made way.
West Ham were unbeaten in their previous four games, form which belied their lowly position, and they looked full of confidence in the opening exchanges despite the absence of Kieron Dyer through injury.
Tim Krul had to make an excellent save from point-blank range to deny former Portsmouth striker Frederic Piquionne early on - although the Frenchman was flagged offside - and it took some scrappy defending to crowd out Carlton Cole as he lined up a shot in the box.
But Piquionne and Cole were both involved as West Ham deservedly went ahead on 12 minutes. Mark Noble played a delicious ball over the top for Piquionne and he scuffed his shot across goal, but Cole slid in, apparently onside, to covert from six yards.
Without a win in three games, since beating Everton in October, it would have been easy for Newcastle to fold after such an early blow, but instead they began to improve almost immediately, displaying purpose and poise to drag themselves back into the game.
And the goal they needed came on 23 minutes when Joey Barton's cross was headed down by the towering Carroll, who dominated aerially all afternoon, for Nolan to send a controlled half-volley past England keeper Rob Green.
United's relief was palpable, and although a fast-paced and open remainder of the first-half was even, the second half was all Newcastle.
Whatever Hughton said to his players at the break clearly worked as they began to hog possession and fashion goalscoring chances, with Carroll forcing a decent save from Green before he left the keeper helpless on 69 minutes.
Again Barton was the creator-in-chief, starting the move with a clever ball using the outside of his right foot for the willing Ameobi to collect. The striker held onto it as Barton advanced, then played a well-weighted return for the number seven, who whipped in a cross which had pace and quality in abundance, allowing Carroll to steer home with his head.
And United ended much the stronger of the two sides as the home fans streamed out of their seats and along Green Street.
Barton saw a shot deflected just over, while Ameobi and Carroll both had efforts which Green could only watch helpess as they went wide.
United played keep-ball for the final few minutes, with the likes of Cheik Tiote and Jonas Gutierrez capable of holding onto the ball for several seconds at a time before finding a team-mate, and never looked seriously in danger of losing their grip on the three points.
The headline writers could get to work long before the final whistle had sounded.