
Verein für Bewegungsspiele Stuttgart 1893 e.V. (tak brzmi pełna nazwa klubu) powstało 2 kwietnia 1912 r. w wyniku fuzji dwóch klubów. Pierwszym z nich był FV Stuttgart, który istniał od 1893 r., jednak sekcję piłkarską stworzył dopiero w 1908 r. (do tego momentu był to klub rugby). Drugim z klubów było FC Krone Cannstatt, istniejące jako klub rugby od 1890 r. (w 1897 r. przekształciło się w klub piłkarski). Do fuzji klubów doszło w hotelu Concordia w Cannstadd (peryferie Stuttgartu). VfB Stuttgart aż do lat 30-tych nie odnosiło żadnych sukcesów. Wszystko zmieniło się w 1933 r., kiedy to III Rzeszę podzielono na 16 lig, zwanych Gauligen. VfB znalazło się w Gauligen Wurttenberg, którą wygrywało w latach: 1935, 1937, 1938, 1940 i w 1943 r. Wówczas rozpoczęła się historyczna walko o przymat w mieście pomiędzy VfB a Stuttgarter Kickers (lokalny rywal został założony w 1899 r., a z racji swoich barw nazywany jest "Die Blauen", czyli "Niebiescy"). Mistrzowie poszczególnych lig po zakończeniu sezonu grali systemem pucharowym o Mistrzostwo III Rzeszy. Najlepszy wynik VfB osiągnęło w 1935 r. kiedy to doszło do finału rozgrywek, gdzie po dramatycznym meczu uległo Schalke 04 Gelsenkirchen 4-6.
Po zakończeniu II wojny światowej rozgrywki piłkarskie w RFN zostały zreorganizowane. Ekipa VfB znalazła się w Oberliga Süd, którą wygrała w 1946, 1952 i 1954 r. W 1950 i 1952 r. klub ze Stuttgartu zdobywał tytuły mistrza Niemiec (rozgrywane wówczas systemem pucharowym). Lata 50-te to bez wątpienia najlepszy okres w historii klubu. Oprócz dwóch mistrzostw piłkarze VfB zdobyli dwa Puchary Niemiec (w 1954 i w 1958 r.). Co ciekawe, ani jeden piłkarz ówczesnej ekipy "Die Roten" nie znalazł się w kadrze reprezentacji RFN, która wywalczyła tytuł Mistrzostwa Świata w 1954 r.
W 1963 r. Niemiecki Związek Piłki Nożnej (DFB) powołał do życia wprowadził nowy tryb rozgrywek piłkarski na terenie RFC. Najwyższą klasą rozgrywkową została Bundesliga. W związku z bardzo dobrymi występami w latach 50-tych, ekipa VfB Stuttgart znalazła się w gronie szesnastu zespołów, które stworzyły oryginalną Bundesligę. Klub był typowym średniakiem ligowym, w związku z tym, iż do lat 60-tych był zaledwie klubem pół-zawodowym i większość piłkarzy oprócz gry w piłkę prowadziła zwykłe życie zawodowe. W sezonie 1972/1973 VfB zakwalifikowało się po raz pierwszy w historii do Pucharu UEFA. W swoim debiutanckim sezonie w europejskich pucharach (1973/74) doszli aż do półfinału, gdzie ulegli ekipie Feyenoordu Rotterdam, który później zdobył puchar. W następnym sezonie klub zmienił całkowicie swoje oblicze i spadł do drugiej ligi niemieckiej. Tuż pod koniec sezonu nastąpiła zmiania władz klubu. Nowym prezydentem klubu został lokalny polityk Gerhard Mayer-Vorfelder.
Pierwszy sezon w 2.Bundesliga ekipa VfB zakończyła na dalekim 11 miejscu. W związku ze słabą grą kibice sporadycznie pojawiali się na meczach "Die Roten". Niechlubny rekord padł podczas meczu z SSV Reutlingen. Na Gottlieb-Daimler-Stadion (mogącym pomieścić blisko 56 tys. widzów) pojawiło się ok. 1200 fanów. W sezonie 1976-1977 piłkarze VfB wywalczyli awans do Bundesligi. Kluczowe role w zespole odgrywali wówczas Karlheinz Föster, Hansi Müller oraz Ottmar Hitzfeld (tak, tak aktualny trener Bayernu Monachium). Pierwszy sezon po powrocie był niezwykle udany i młody zespół zajął wysoką, czwartą lokatę w lidze. VfB prowadzone przez Hansa-Jürgena Sundermanna słynęło z bardzo ofensywnej gry i spotkań, w których padało mnóstwo bramek. Średnia widzów na spotkaniach ligowych na własnym stadionie wynosiła 53 tysiące! Następny sezon był jeszcze bardziej udany i klub zakończył go na drugiej pozycji. W sezonie 1979/1980 VfB doszło po raz drugi w historii do półfinału Pucharu UEFA.
Lata 80-te to kolejne bardzo dobre występy klubu ze Stuttgartu. W 1984 r. VfB zdobyło swój trzeci tytuł Mistrza Niemiec. W 1986 r. doszło do finału Pucharu Niemiec, gdzie uległo Bayernowi Monachium 2-5. W 1989 r. "Die Roten" doszli do finału Pucharu UEFA. Ich przeciwnikiem było SSC Napoli, w których szeregach grał Diego Maradona. Włoski klub wygrał w dwumeczu 5-4. W 1992 r. VfB zostało po raz czwarty Mistrzem Niemiec. Tytuł ten zdobyli dzięki lepszej różnicy bramek od Borussii Dortmund. W następnym sezonie zespół bardzo szybko pożegnał się z Pucharem Europy, w którym odpadł w pierwszej rundzie przegrywając z Mistrzem Anglii, Leeds United.
Następny raz piłkarze VfB pojawili się na arenie międzynarodowej w sezonie 1997/1998 po tym jak zdobyli Puchar Niemiec. Powrót na europejskie stadiony był niezwykle udany i zakończył się udziałem w finale nieistniejącego już Pucharu Zdobywców Pucharów. VfB Stuttgart przegrało w decydującym meczu z Chelsea Londyn. W 2000 r. z funkcji prezydenta klubu zrezygnował Gerhard Mayer-Vorfelder, który znalazł zatrudnienie w DFB. Z jego odejściem zakończyła się tzw. "M-V Era". Ustępujący prezydent zostawił jednak klub, którego szkółka piłkarska do dziś uznawana jest za najlepszą w Niemczech.
W 2001 r. po bardzo słabym sezonie (zaledwie 15 miejsce w tabeli) z klubu został zwolniony Ralf Rangnick, a jego następcą został Felix Magath, który oparł zespół na młodych wychowankach klubu. To dało bardzo szybkie efekty i w sezonie 2002/2003 klub został wicemistrzem Niemiec. W następnym sezonie VfB uczestniczyło w rozgrywkach Ligi Mistrzów. W rozgrywkach grupowych musiało uznać wyższość Manchesteru United, ale okazało się lepsze od Panathinaikosu Ateny i Rangers FC. W następnej fazie (runda pucharowa) niemieccy piłkarze stoczyli bardzo wyrównany bój z Chelsea Londyn i ulegli w dwumeczu zaledwie 0-1. Po tak znakomitych występach Felix Magath skusił się na ofertę Bayernu Monachium, a nowym szkoleniowcem został Giovanni Trapattoni. Włoski trener został jednak zwolniony w trakcie sezonu 2005/06 w związku z bardzo słabymi wynikami zespołu. Jego następcą został Armin Veh, który do dziś znajduje się na tym stanowisku. W zeszłym sezonie VfB Stuttgart po dramatycznym finiszu Bundesligi wyprzedziło ekipę Schalke 04 Gelsenkirchen, zdobywając piąty tytuł Mistrza Niemiec. Oprócz mistrzostwa piłkarze z Gottlieb-Daimler-Stadion mieli szansę na zdobycie Pucharu Niemiec, jednak w finale ulegi ekipie FC Nürnberg.
Barw VfB Stuttgart na przestrzeni lat bronili tacy piłkarze jak: Krassimir Balakov, Thomas Berthold, Fredi Bobic, Guido Buchwald, Carlos Dunga, Giovanne Elber, Srecko Katanec, Matthias Sammer, Svonimir Soldo, Thomas Strunz oraz przede wszystkim Jürgen Klinsmann.