Peter Crouch's opener and a Marko Arnautovic stunner, either side of a Robin Van Persie equaliser, looked to have been enough for the visitors to claim their biggest top-flight scalp in half a century.
However, City's hearts were broken just ten minutes from full-time as firstly Wayne Rooney looped a header in from an acute angle to level matters, before substitute Javier Hernandez nodded into an empty net 90 seconds later to clinch victory for the champions.
Mark Hughes made three changes to his starting eleven prior to kick-off, as he seeked to inflict another Old Trafford upset upon his former employers, who had already dropped points on home turf against West Brom and Southampton during the campaign.
Wilson Palacios made his first league start of the season in central midfield, replacing Charlie Adam, whilst Crouch and Geoff Cameron, who overcame a calf problem, were both recalled into the eleven after missing the goalless draw with the Baggies seven days earlier.
Hughes' confession that he hadn't yet found the right combination up front led to a recall for Crouch, with summer acquisition Marko Arnautovic moving out into a more familiar role on the left hand side of a front three.
Meanwhile, American international Cameron replaced Andy Wilkinson at right back, after overcoming a late fitness test on an injury he sustained during international duty two weeks ago.
The Potters' hopes of recording victory were given a major boost just three minutes into the game as an exquisite run from Dutch international Erik Pieters culminated in Crouch prodding home the opening goal of the afternoon, after David De Gea pulled off a sensational point-blank save to initially thwart the frontman.
If anything though that early strike looked to have given David Moyes' side even more incentive to bounce back and reignite their stuttering campaign that had resulted in just 11 points being recorded from their initial eight encounters.
Patrice Evra fired high and wide of Asmir Begovic's goal from range, whilst two delicious balls across the box from Robin Van Persie failed to connect with one of the large numbers of United players hovering inside the danger zone.
At the other end, Crouch went agonisingly close to doubling the visitors advantage after volleying inches over the bar from 8-yards following a clever pull back from Walters at the far post.
A succession of corners pegged the Potters back as the hosts threw everything at Shawcross and co at the back, but in true Stoke style the rearguard had answers for all of the questions being posed of them by United.
As the first half wore on you could sense the sheer desperation within the United ranks as both Rooney and Van Persie were guilty of snapping at half chances from distance, as they struggled to forge an avenue through a dogged and determined Stoke backline.
It was far from all one way traffic however as Hughes' side continued to threaten on the break, and again should have given themselves an even bigger lead when Crouch and Walters combined brilliantly inside the 18-yard box to forge a clear sight at goal, only for De Gea to deny Walters with a great save down to his left.
The Republic of Ireland ace then turned provider with a sublime deep cross from the right which found the boot of Arnautovic, who was sadly unable to make the sort of connection he would have liked to have really threatened the goal of United's Spanish stopper.
It wasn't until ten minutes before the interval that Begovic was called into action for the first time - producing a stunning fingertip save to flick Rooney's thunderous 30-yard effort over the bar and into the Stretford End.
Minutes later the Bosnian was at his brilliant best yet again to deny Rooney from inside the 6-yard box, but heartbreakingly the ball fell straight into the path of Van Persie who rifled home an undeserved leveller.
Que the wild celebrations and undoubted renewed optimism amongst the majority of the 70,000 plus supporters inside the stadium.
Well, not quite, as Arnautovic produced a moment of absolute genius with a wonderfully taken free-kick from the edge of the penalty area to restore the visitors advantage right on the stroke of the half-time whistle.
Sadly, that proved to be his final influence on the match as an apparent twinge to his led leg to him leaving the field just four minutes into the second half, with Marc Wilson coming on as his replacement.
The hosts failed to raise their game significantly following what must have been a stern half-time talking to from former Everton boss Moyes, so he responded by thrusting teenage starlet Adnan Januzaj into the mix in a bit to revive his side's hopes of claiming maximum points for only the second time on home soil this campaign.
The young Belgian forward ignited the hosts, and they began to play with the same fluidity and aggression that led to them reclaiming the Premier League crown from city rivals Manchester City last term.
That said they were still having major difficulties in finding a way through the Potters rearguard, and it wasn't until Rooney produced a header of sublime quality and accuracy twelve minutes from time that United looked likely of claiming something from the game.
The England stars goal gave fresh belief to his side that the could come from behind and record a win that their performance hadn't deserved.
Stoke were rocked by the goal, and agonisingly fell behind just 90 seconds later as Patrice Evra's stunning centre from the left was met by the head of Hernandez, who had the simplest of tasks of putting the ball into an empty net from just two-yards out.