Klubben blev reelt først dannet i 1912, da Stuttgart FV 93 og Kronen-Club Cannstatt fusionerede, men da førstnævnte var grundlagt i 1893 valgte man at anse VfB som en direkte efterfølger.
VfB Stuttgart havde masser af succes inden 2. verdenskrig, men første mesterskab blev først vundet i 1950. I alt fire gange har klubben kunnet kalde sig "Tysklands bedste". Klubben har en naturlig rivaliserende klub, Stuttgarter Kickers, men i de seneste mange år har Kickers ligget i de mindre ligaer.
Stuttgart tabte egentlig 1-4, men havde benyttet en fjerde udlænding, hvilket var ulovligt på det tidspunkt. Resultatet blev omstødt til 3-0 til Leeds. Da det gav et lige resultat, blev en afgørende kamp spillet i Barcelona, som Leeds vandt 2-1.