باشگاه ورزشی اشتوتگارت از بدو تأسیس در رشتههای ورزشی مختلفی فعالیت میکرد. اولین تیم ورزشی این باشگاه، راگبی بود که در سال ۱۸۶۵ میلادی تشکیل شد. اما تیم فوتبال این باشگاه حاصل تلفیق چند تیم مختلف در این باشگاه است که سرانجام منجر به ایجاد باشگاه فوتبال اشتوتگارت شد. در ۹ سپتامبر ۱۸۹۳ این باشگاه با نام ایف. وی اشتوتگارت تأسیس و فوتبال را در سطح آماتور پیگیری میکرد. در سال ۱۹۱۲ تیم فوتبال حرفه ای کانشتات با این باشگاه تلفیق شد و از آن پس نام باشگاه به فا. ایف. ب اشتوتگارت تغییر پیدا کرد.
دهه ۱۹۴۰ و ۱۹۳۰ در ابتدا باشگاه اشتوتگارت در سطح لیگ ایالتی حضور داشت و چند بار هم در این برهه به مقام قهرمانی رسید. در سال ۱۹۳۳ باشگاه به نِکِر استادیوم نقل مکان کرد. در همان سال سازمان فوتبال آلمان تحت نظر رایش سوم تغییر نمود و به ۱۶ دسته در نواحی مختلف آلمان به نام گائولیگن تقسیم شد. اشتوتگارت در این زمان موفقیتهای چشمگیری در لیگ منطقه ای گائولیگن بادن وورتمبرگ به دست آورد و در سالهای ۱۹۳۵، ۱۹۳۷، ۱۹۳۸، ۱۹۴۰ و ۱۹۴۳ قهرمان این مسابقات شد. سرانجام در فصل ۴۵–۱۹۴۴ و در پی جنگ جهانی این مسابقات تعطیل شد. در این دوره اشتوتگارت رقابت سختی با تیم همشهری خود، اشتوتگارتر کیکرز داشت. قهرمانی مداوم در لیگ منطقه ای باعث شد تا اشتوتگارت بتواند به مراحل بالاتر لیگ ملی راه پیدا کند. بهترین نتیجه آنها در سال ۱۹۳۵ رقم خورد، جایی که در فینال لیگ ملی مقابل شالکه، مدافع عنوان قهرمانی با نتیجه ۶–۴ شکست خورد و به نایب قهرمانی رسید. در سال ۱۹۳۷ هم اشتوتگارت به مقام سوم لیگ ملی رسید و این آخرین موفقیت آنها در این برهه زمانی بود.
دهه ۱۹۵۰ پس از پایان جنگ جهانی دوم اشتوتگارت در سطح اول فوتبال آلمان حضور پیوسته داشت و توانست در اوبر لیگای جنوب در سالهای ۱۹۴۶، ۱۹۵۲ و ۱۹۵۴ به قهرمانی این لیگ ایالتی برسد. اشتوتگارت همچنین در لیگ ملی آلمان هم در سالهای ۱۹۵۰ و ۱۹۵۲ به مقام قهرمانی رسید و در سال ۱۹۵۳ هم نایب قهرمان این مسابقات شد. موفقیتهای اشتوتگارت در این دهه با قهرمانی در جام حذفی فوتبال آلمان موسوم به دی.اف.بی.پوکال در سالهای ۱۹۵۴ و ۱۹۵۸ ادامه پیدا کرد. تیمی که توانست طی ۸ سال، ۴ قهرمانی در سطح اول فوتبال آلمان برسد. اشتوتگارت در این سالها به رهبری بازیکن اسطوره ای خود، رابرت شلینز که دست چپ خود را در حادثه رانندگی از دست داده بود، حریفان را یکی پس از دیگری از پیش روی برمیداشت.
تاسیس بوندسلیگا به دلیل نتایج ناامید کننده در جامهای جهانی ۱۹۵۸ و ۱۹۶۲ که توسط تیم ملی آلمان به دست آمد و در پی رشد حرفه ای گری در ورزش، اتحادیه فوتبال آلمان (دی.اف. بی) تصمیم گرفت تا لیگهای مجزای منطقه ای را با یک لیگ سراسری ملی در سال ۱۹۶۳ جایگزین کند. نتایج درخشان اشتوتگارت در دهه ۵۰ باعث شد تا این تیم جزو ۱۶ تیمی باشد که در اولین دوره بوندسلیگا حضور داشته باشد. اشتوتگارت از آغاز بوندس لیگا تا اواسط دهه ۷۰ میلادی، معمولاً در میانههای جدول حضور داشت. یکی از معدود ستارگان آن روزهای باشگاه گیلبرت گِرِس، هافبک مهاجم فرانسوی بود که از باشگاه استراسبورگ جذب شده بود. در سال ۱۹۷۳، اشتوتگارت برای نخستین بار سهمیه حضور در جام یوفا را کسب نمود و در سال ۱۹۷۴ تا نیمه نهایی این رقابتها پیشروی نمود و با شکست مقابل فاینورد ، قهرمان رقابتها، از این جام کنار رفت.
۱۹۷۵ تا ۲۰۰۰ باشگاه اشتوتگارت تا اواسط دهه ۷۰ میلادی در بحران نسبی به سر میبرد. دوران جدید فوتبال و بالا رفتن سطح حرفه ای در فوتبال و به وجود آمدن مقولههای جدیدی همچون اسپانسرشیپ در فوتبال، با وجود هزینههای باشگاه با شکست مواجه شده شده بود. در پایان فصل ۷۴–۱۹۷۳، اشتوتگارت خطر سقوط به بوندسلیگا ۲ را حس نمود. در این سال سیاستمدار محلی، گرهارد مایر ورفلدر به سمت ریاست باشگاه برگزیده شد. تساوی در بازی پایانی فصل بدین معنی بود که اشتوتگارت به بوندس لیگا ۲ سقوط کردهاست. در فصل بعد اشتوتگارت بدترین نتیجه تاریخ خود را گرفت و در بوندس لیگا ۲، در رده یازدهم قرار گرفت. در فصل ۷۶–۱۹۷۵ با آمدن مربی جدید، یورگن ساوندرمان و استعدادهای جدیدی چون کارل هاینتس فورستر ، هانسی مولر و اوتمار هیتسفلد ، اشتوتگارت توانست با رکورد ۱۰۰ گل زده، پس از دو فصل دوباره به بوندسلیگا ۱ بازگردد. تیم جوان به خاطر نوع بازی هجومی و تعداد گلهای پرشماری که به ثمر میرساند، محبوب بود. در این میان اما کم تجربگی در تیم حس میشد. در پایان فصل ۷۸–۱۹۷۷ اشتوتگارت در رده چهارم لیگ قرار گرفت و رکورد تعداد تماشاگران را با میانگین ۵۳ هزار نفر در یک فصل ثبت کرد که این رکورد تا سال ۱۹۹۰پابرجا بود. در سال ۱۹۸۰ اشتوتگارت دوباره تا نیمه نهایی جام یوفا پیش رفت و در جمع چهار تیم برتر لیگ قرار گرفت. ادامه همین روند باعث شد تا در سال ۱۹۸۴ و تحت هدایت هلموت بنتاوس، اشتوتگارت پس از سالها دوباره قهرمان بوندس لیگا لقب بگیرد. در سال ۱۹۸۶، اشتوتگارت در فینال جام حذفی، ۵–۲ مغلوب بایرن مونیخ شد و به نایب قهرمانی این جام رسید. در سال ۱۹۸۹ نیز اشتوتگارت با بازیکنانی چون یورگن کلینزمن در فینال جام یوفا مقابل ناپولی که ستارگانی چون دیگو مارادونا را در ترکیب داشت قرار گرفت و در مجموع دو بازی ۵–۴ مغلوب شد و به نایب قهرمانی این رقابتها بسنده کرد. در فصل ۹۲–۱۹۹۱ اشتوتگارت در یکی از سختترین، فشردهترین و نزدیکترین فصول تاریخ بوندس لیگا، با هدایت کریستوف دام توانست در رقابت با بروسیا دورتموند ، چهارمین قهرمانی خود در لیگ سراسری را با تفاضل گل بهتر دست بیاورد. در فصل ۹۳–۱۹۹۲ اشتوتگارت در لیگ قهرمانان اروپا حضور یافت و توانست در دو بازی لیدز یونایتد را از پیش رو بردارد، اما به علت استفاده از بیش از ۳ بازیکن غیر آلمانی در دیدار برگشت، (قانون وقت اجازه حضور بیش از ۳ بازیکن غیربومی را نمیداد)،کار به بازی سوم کشید؛ بازی سوم در زمین بیطرف در بارسلونا برگزار شد که با حذف عجیب اشتوتگارت همراه بود. اشتوتگارت تا سال ۱۹۹۷ نتوانست به رقابتهای اروپایی راه پیدا کند. در این فصل با هدایت یوآخیم لوو اشتوتگارت به سومین قهرمانی خود در جام حذفی دست یافت. در سال ۱۹۹۸ اشتوتگارت توانست به فینال رقابتهای جام برندگان جام اروپا در استکهلم راه یابد که در دیدار نهایی مغلوب چلسی انگلیس شد و بار دیگر به نایب قهرمانی در یک رقابت اروپایی رسید. سه بازیکن برتر اشتوتگارت در آن سالها که به مثلث جادویی شناخته میشدند، شامل کراسیمیر بالاکوف، جیووانی اِلبر و فردی بوییچ بود. به جز بالاکوف، دو نفر دیگر اشتوتگارت را ترک کردند و قرارداد یوآخیم لوو نیز در پایان فصل تمدید نشد تا شاهد پایان یک دوره باشیم. وینفرد شفر جایگزین لوو شد و پس از یک فصل اخراج گردید. در طی دو فصل آینده اشتوتگارت در ردههای میانی جدول قرار گرفت و موفقیت خاصی کسب نکرد.