Erstmals urkundlich fassbar wird eine Cannstatter Mühle in den „Altwürttembergischen Urbaren“. Die in diesen um 1350 entstandenen Lagerbüchern genannte Mühle muss an demselben Standort vermutet werden, an dem sich noch bis 1882 die Cannstatter Stadtmühle befand, also knapp unterhalb der Wilhelmsbrücke außen an der Stadtmauer. Die Stadtmühle war im Jahre 1605 aus der Vereinigung der ursprünglich dort befindlichen Mühle mit zwei weiteren Cannstatter Mühlen entstanden. Eine der beiden hatte sich im Bereich der heutigen Flurstraße unter dem König-Wilhelm-Viadukt befunden, was damals natürlich weit außerhalb der Stadt lag. Nach einem dortigen Gewann nannte man dieses ebenfalls durch die Stadt Cannstatt betriebene Werk Flurmühle. Anders als in der ortskundlichen Literatur hier und dort zu lesen ist, bezog die Flurmühle ihr Antriebswasser aus dem Neckar, was auch eine Zeichnung Heinrich Schickhardts deutlich macht.
Die andere der beiden Mühlen, die in der Stadtmühle aufgingen, war die Sulzmühle. Sie bezog ihr Antriebswasser teils von der sogenannten Rathaussulz, einem kleinen Mineralwassersee nahe dem alten Rathaus, dessen Wasser verzweigt durch die Gassen Cannstatts geleitet wurde, bevor man es in den Stadtgraben abfließen ließ, teils auch von einer Sulz vor dem Oberen Tor, also im Bereich des heutigen Wilhelmsplatzes. Anders als die Flurmühle gab man die Sulzmühle nach der Erbauung der großen Stadtmühle am Neckar nicht für immer auf. Im Laufe der Zeit sollte sie noch verschiedene Nutzungen erleben: Zu Beginn des 18. Jahrhunderts hören wir von einer Ölmühle an diesem Ort, dann plante man die Einrichtung einer Strumpfwalke, was den Protest des Pächters einer staatlichen Walkmühle am Berger Mühlkanal auslöste. Noch einmal hundert Jahre später fand die alte Sulzmühle dann eine neue Bestimmung als Sägewerk. Eine mit dieser Anlage verbundene Tabakmühle wurde später durch eine Öl- und Obstmühle ersetzt. Dem Triebwerk wurde in dieser Zeit eine weitere Kraftquelle erschlossen, indem man Wasser vom Sulzerrain beim späteren Kursaal in einem teilweise überdeckten Kanal herbeileitete. Der Standort der Sulzmühle war die äußerste nordöstliche Spitze der Altstadtummauerung, im untersten Bereich der heutigen Wilhelmstraße.
Als das Holz- und Ölgeschäft Mitte des 19. Jahrhunderts eine Flaute erlebte, begann man in der alten Sulzmühle als zusätzliches Betätigungsfeld mit der Graupenproduktion. Zunächst erfolgte eine Einsprache seitens der Stadtmühle, die damals ähnliche Pläne verfolgte, doch schließlich konnten die erforderlichen Maschinen eingebaut und in Betrieb genommen werden. Im Vergleich zur auch in Cannstatt sich schon rasant entwickelnden Industrie war die alte Sulzmühle in jener Zeit von eher geringer wirtschaftlichen Bedeutung: Die Säg-, Öl- und Obstmühle samt neuer Graupenrolle war im Steuerregister niedrig eingestuft, da sie aufgrund von Wassermangel höchstens sechs Monate im Jahr betrieben werden konnte, und selbst dann immer nur mit jeweils einer Maschine gleichzeitig. Um die Wende zum 20. Jahrhundert hören wir zum ersten Mal von einer Dampfmaschine an diesem Standort, bevor das Gebäude kurze Zeit später der Modernisierung weichen musste.
Bei dem Antrieb der alten Sulzmühle durch das in Cannstatt so reichlich fließende Mineralwasser handelt es sich übrigens keineswegs um eine Behelfslösung. Auch die große Neckarmühle an der Brücke besaß ein verbrieftes Recht darauf, der Sulzmühle zu gewissen Zeiten das Quellwasser zu entziehen und es auf ihre eigenen Räder zu leiten. Der Grund hierfür ist nicht in einer Verstärkung durch die vergleichsweise schwachen Quellen der Altstadt zu sehen. Vielmehr hielt das ganzjährig gleichmäßig temperierte Sulzwasser die Mühlräder im Winter eisfrei.
Als ab 1830 mit dem Aufkommen der großen wassergetriebenen Fabriken die uralte Technik der „Warmwasserbenutzung“ in größere Maßstäbe transponiert werden musste, begann man nach dem Vorbild von England und Frankreich, auch in Berg und Cannstatt Wasserquellen künstlich zu erbohren. Wegen des geologisch zusammenhängenden Bodenwassersystems führte das Erschließen neuer Brunnen zu einem Nachlassen der natürlichen Mineralquellen, was für die Kur- und Bäderstadt Cannstatt fatal sein musste. Das Bohren in der Umgebung schadete zudem den zuletzt erbohrten Quellen der Mühlen und Fabriken, sodass weitere private Bohrungen bald behördlich untersagt wurden.
Wie bereits erwähnt, leitete man ab Beginn des 19. Jahrhunderts zusätzliches Wasser vom Sulzerrain herbei, um damit die Antriebskraft für das Rad der Sulzmühle zu verstärken. Im Jahre 1773 hatte man dort, weit vor den Toren der Stadt, auf der Suche nach Salz eine natürliche Quelle verstopft und in über 60 Meter Tiefe den später so genannten Wilhelmsbrunnen erbohrt. Da jedoch der Salzgehalt des Wassers geringer als erwartet war, ließ man es unbenutzt abfließen. Erst über zehn Jahre später ging bei den Behörden das Gesuch eines Zimmermanns und eines Schmiedes ein, mit dem Wasser eine gemeinsame Ölmühle und Hanfreibe am Sulzerrain betreiben zu dürfen. Dies wurde u.a. damit begründet, dass die nächste Ölmühle sich in Esslingen befinde, für eine Hanfreibe müssten die Seilermeister sogar bis Pforzheim ziehen.
Zu Beginn des 19. Jahrhunderts wurde die Ölmühle am Sulzerrain modernisiert und erweitert, während man die Hanfreibe aufgab. Auf lange Sicht setzte man die Hoffnungen aber auf das Handelsgeschäft mit fertigem Öl. Diese Tendenz war auch durch die Unzuverlässigkeit der Maschinen bei nachlassender Wasserschüttung der Quelle motiviert. So war das Schicksal der Mühle am Sulzerrain abzusehen, als König Wilhelm schließlich 1822 das Anwesen erwarb, um hier den Kurpark anlegen zu lassen. Das Ölmühlgebäude wurde abgerissen und das Gelände am Fuße der Anhöhe mit dem Kursaal überbaut. Als Ersatz für diese Mühle erweiterte einige Jahre später der Betreiber der Sulzmühle im Stadtgraben sein Sägewerk um die erwähnte Ölmühleneinrichtung.
Um 1830 galt die Stadtmühle an der Neckarbrücke insgesamt als unrentabel. Man hatte immer wieder umfangreiche Baumaßnahmen zu bewältigen gehabt, zu den üblichen Reparaturen aufgrund von Verschleiß kamen regelmäßig Hochwasserschäden. Nachdem die Stadt schon die Versteigerung des Betriebes eingeleitet hatte, schlug man schließlich doch einen anderen Weg ein, und der Pächter investierte beträchtliche Summen in seine Mühle, wobei er dem Vorbild anderer Betriebe, vor allem der sogenannten Kunstmühle in Berg, folgte: Zur neuen Ausstattung gehörten u.a. zwei Koppgänge, also Maschinen zur Getreidereinigung, eine Grießputzmaschine, eine Schwingmühle und Körneraufzüge. Doch trotz aller Modernisierungsmaßnahmen war das Gebäude im Kern schon mehrere hundert Jahre alt und wurde 1869 außerdem durch einen Brand beschädigt. In den Jahren 1880 bis 1884 wurde die Cannstatter Stadtmühle ein kurzes Stück kanalabwärts, gegenüber der Mühlgrüninsel etwa beim heutigen Eingang zur Stadtbücherei, völlig neu erbaut.
Nach den Zerstörungen im Zweiten Weltkrieg konnte 1951 in der Überkinger Straße 19 eine neue große Stadtmühle mit elektrischem Antrieb in Betrieb genommen werden. Auf dem benachbarten Grundstück, dem Standort der Mühle von 1884 und ihres Nebengebäudes, entstand Anfang der 1960er Jahre ein Lagergebäude. Der Mühlbetrieb musste 1993 wegen veralteter Einrichtung und ungünstiger Verkehrslage eingestellt werden. Heute befindet sich in dem markanten Hochbau eine Seniorenresidenz, während das lang gestreckte Nebengebäude u.a. die Stadtbücherei beherbergt.