Die beiden Dörfer Mühlhausen und Ehingen im Hegau wurden im Jahre 787 erstmals urkundlich in einer Schenkungsurkunde des Klosters St. Gallen genannt. Der Ort Mühlhausen ist aus zwei Siedlungen - dem Unterdorf, welches zur Herrschaft Mägdeberg gehörte, und dem Oberdorf, das der Herrschaft Hohenkrähen untertänig war, zusammengewachsen.
Südwestlich von Mühlhausen erhebt sich als trutzige Basaltkuppel der Mägdeberg, der schon in der Hallstadtzeit (ca. 900 v. Chr.) eine Keltensiedlung trug. In den Jahren 1230 - 1340 erbauten die Äbte des Klosters Reichenau auf dem Mägdeberg eine Burg. Mühlhausen und Ehingen gehörten bis zum Hochmittelalter dem Kloster Reichenau an. Durch den Adel jedoch, kamen diese zu verschiedenen Herrschaften. Württemberger, Habsburger, die Freiherren von Rost, zum Schluss die Grafen von Langenstein, waren Grundherren von Mühlhausen. Die Edlen von Hewen, die Lupfer und die Pappenheimer übten die Grundherrschaft über Ehingen aus. Zu letzt waren es die Fürsten zu Fürstenberg.
Nach der Christianisierung des Landes, wurden die drei Heidemägde "Ainbed, Borbed und Wilbed", aus deren Namen der Name des Mägdebergs entstand, durch die hl. Ursula mit ihren Gefährtinnen, die nachweislich verehrt wurden, ersetzt.
Sowohl Mühlhausen als auch Ehingen wurden durch Kriege sowie den ständigen Wechsel der Herrschaften schwer in Mitleidenschaft gezogen. In der Zeit von 1378 bis 1499 brannte Mühlhausen viermal ab. Ehingen ist im Verlaufe des Schweizerkrieges, des Bauernkrieges und zuletzt unter Napoleon am 03. Mai 1800 fast völlig zerstört worden.
Als die beiden Dörfer Mühlhausen (1810) und Ehingen (1805) dem Großherzogtum Baden eingegliedert wurden, trat für die Bevölkerung eine Verbesserung der Verhältnisse ein.
Die beiden Weltkriege forderten viele Opfer aus der Gemeinde. Die Nachkriegszeit jedoch, brachte eine völlige Neustrukturierung des Ortes.
Bei der Gemeindereform in den 70er Jahren schlossen sich die beiden, damals noch eigenständigen, Gemeinden zur Doppelgemeinde Mühlhausen-Ehingen zusammen.