Die Teichsmühle ist die erste urkundlich belegte Mühle in der Stadt Soest. Sie wurde erstmals 1231 als Eigentum des St.-Patrokli-Stiftes erwähnt, das sie als Lehen an eine adlige Familie vergab.
Der Zeitpunkt der Entstehung ist unbekannt, wahrscheinlich in der zweiten Hälfte des 12. Jahrhunderts, da in dieser Zeit die Eindämmung des Großen Teiches als Staubecken für die Mühle stattgefunden hat. Im 14. Jahrhundert waren sechs Mühlen innerhalb der Stadtmauern in Betrieb, die vom Wasser der Quellen angetrieben wurden. Noch im 17. Jahrhundert wurden diese als Besonderheit der Stadt Soest beschrieben. In der "Specification der Soester Mühlen" aus dem Jahr 1738 waren innerhalb der Stadt und der Börde 37 Mühlen aufgelistet. Die meisten davon wurden als Getreidemühlen klassifiziert, was die Bedeutung der Soester Börde als Getreidelandschaft noch in der frühen Neuzeit deutlich macht.
Die Teichsmühle wurde in den 1930 Jahren nach Plänen von Paul Schlipf im Stil der Heimatschutzarchitektur verweitert.