Prvními obyvateli byli římští vojáci, kteří vybudovali na území dnešní městské čtvrti Bad Cannstatt obranáobranná [[Castrum|castra]] a to okolo roku 90 n.l. Ve 3. století vytlačil Římany germánský kmen [[Alamani|Alamanů]] a území zůstalo neosídlené do 9. století. V roce 950 n.l. vévoda Liudolf Švábský, syn císaře [[Svatá říše římská|Svaté říše římské]] [[Ota I. Veliký|Oty I.]], se rozhodl na opuštěném území založit hřebčinec. Osada měla chovat koně pro jeho armádu, která bojovala proti [[Maďarský vpád do Evropy|maďarské invazi z východu]]. Osada je zmíněná v kronikách v letech 1108 a 1160, ale stále jen jako pár stavení. Rozvoj nastal až po předání oblasti do rukou rodu [[Württemberkové|Württemberků]] v roce 1251. Město se začalo rozrůstat a následně do něj hrabě Eberhard I. přenesl v roce 1320 sídlo rodu, vybudoval hradby a přiřkl Stuttgartu městská práva.