A week after securing a place in the FA Cup semi-finals, Tony Pulis' side cruised past the Tynesiders with a clinical display which moved them above their opponents and into the top half of the table.
Jon Walters opened the scoring after 28 minutes and the floodgates opened after the break with Jermaine Pennant, Danny Higginbotham and Ricardo Fuller completing the rout.
Newcastle have taken just one point from their last three games and may now start looking over their shoulders with only a four-point buffer separating them from the relegation zone.
It proved an unhappy return to the side for Sol Campbell, in for Steven Taylor in one of three changes to the team that lost to Everton.
Joey Barton was back after a thigh injury with Jonas Gutierrez stepping down while Shola Ameobi was preferred to Leon Best.
Goalkeeper Asmir Begovic returned between the posts for Stoke with Thomas Sorensen back on the bench.
It was Newcastle who were the first to show with Ameobi turning quickly in the fifth minute and firing a shot into the body of Begovic.
Five minutes later Ameobi won a free-kick out on the left after he had been tripped by Marc Wilson.
Barton delivered the ball into the area but it was easily cleared to safety.
Stoke responded in the 12th minute and Wilson got clear of his marker only to head wide of the post from Pennant's corner.
Then Rory Delap launched a long throw into the area in the 17th minute and Newcastle goalkeeper Steve Harper took no chances, punching the ball clear.
It was an even game at this stage and Jose Enrique scampered forward for the visitors four minutes later but his delivery was poor and Ryan Shawcross cleared comfortably.
Enrique seemed to pick up a knock and was immediately replaced by Shane Ferguson.
Stoke took the lead in the 27th minute when Newcastle failed to deal with a cross from Pennant. Walters was the first to react and send a header over Harper for his eighth goal of the season.
However Newcastle made a spirited response and Barton fired a free-kick narrowly over the bar.
The visitors kept up the pressure and Kevin Nolan carved out a good opportunity moments later. His cross took a deflection and looped over Begovic but the keeper managed to get a hand to it and divert the ball away.
Nolan was then dazed following a challenge by Walters but soon recovered.
Newcastle were beginning to look dangerous as half-time approached and Ferguson got in a good header only for Begovic to be equal to it.
Stoke extended their lead just a minute into the second half thanks to a string of defensive errors by Newcastle.
Harper failed to clear properly and Matthew Etherington eventually swung a cross in from the left.
The ball took a deflection and Campbell back-headed it but only into the path of Pennant, who made no mistake.
Former England defender Campbell was left shaking his head in disbelief at making such a basic mistake.
Three minutes later Stoke made it 3-0 with Newcastle again all at sea at the back.
Higginbotham drove a free-kick straight through the wall and past Harper who was rooted to the spot.
Pardew by this point was out in his technical area with a look of bewilderment at how the game had suddenly unfolded.
Newcastle hit back and Ferguson skipped past two defenders in the 66th minute but saw his effort blocked by Begovic.
Campbell was then replaced in the 66th minute by Gutierrez as Newcastle tried to get some kind of hold on the game.
Newcastle were determined to save face and Barton whipped in a free kick after 78 minutes and Begovic did well to turn away at the post.
However Stoke were content to sit deep and let the visitors come onto them near the end of the game.
Stoke completed a convincing victory thanks to a fourth goal from substitute Fuller in stoppage time. Fuller got on the end of a pass from Walters to thump a shot beyond Harper.