Jupp Heynckes' side looked to be cruising at the Olympiastadion but Martin Harnik struck twice late on in a thrilling DFB-Pokal final.
A Thomas Muller penalty and Mario Gomez's double ensured that the Bavarians made history in 68-year-old Juup Heynckes' final game in charge of the club. Martin Harnik struck twice late on to ensure a nervy finish but the European champion held on.
The match started at break-neck pace and, unsurprisingly, it was Bayern which crafted the first chance, with Arjen Robben swapping passes with Franck Ribery and bearing down on Sven Ulreich, who was able to palm the Dutchman's cross-shot around the post.
Gradually, though, Stuttgart was able to get a foothold in the game and, were it not for some wasteful finishing, the club could well have gone ahead.
Their first sight of goal came just before the 10-minute mark, when Ibrahima Traore peeled off his marker and sent a great ball in towards Alexandru Maxim, but the Romanian youngster was only able to steer a volley inches wide of Manuel Neuer's post.
Bayern looked sloppy and a poor back pass from Javi Martinez almost had Manuel Neuer in hot water but David Alaba scampered across to shepherd the ball away from the looming attackers.
Harnik played in Maxim, who was only denied a sure goal by a brilliant Bastian Schweinsteiger tackle, but Vfb's best chance was yet to come.
A Vedad Ibisevic header took a hefty deflection off Manuel Neuer, who could only parry the ball to Georg Niedermeier a coupe of yards from goal but the former Schalke keeper was able to scramble across and keep it out of the net.
The near miss served as a wake-up call for Bayern, which rallied and soon had two great chances to take the lead. Muller slipped in Alaba, who shot straight at Ulreich when he should have scored. The Austrian youngster found himself one on one minutes later, but elected to square the ball, allowing Stuttgart to clear.
Bayern was left furious on 31 minute when Robben was scythed down by Serdar Tasci, only for the referee to give a corner rather than a penalty, but those protests were soon forgotten.
Soon after, Philipp Lahm charged into the box and went down under pressure from Traore. The official duly awarded a spot kick and Muller stepped up to send Ulreich the wrong way.
Minutes into the second half, Robben slipped the ball into the right-hand channel to Lahm, who squared the it to Gomez. The former Stuttgart striker was left with the simple task of bundling into an empty net.
Bruno Labbadia's men had the wind knocked out of their sails and, soon enough, it was three. Muller got down the right once more and squared it to Gomez, who grabbed his second.
Alaba had a shot charged down second later and Heynckes' side was threatening to run away with it but Stuttgart saved some face with 19 minutes remaining. Gotoku Sakai sent in a cross to Harnik who headed home to muted celebration.
The Austrian soon raced down the right and squared it to Shinji Okazaki and claims for a penalty against Jerome Boateng were waved away before Harnik set up a grandstand finish, lashing home the rebound of his own shot, which Neuer had parried.
Bayern was made to endure a nervous ending to the game but held on to make history.