Anfang der 1980er -Jahre in der Martinskirche durchgeführte Ausgrabungen belegen bereits die Römer in Müllheim gesiedelt haben. Die Kirche auf Mauerresten eines römischen Gebäudes errichtet. Auch Zeit der Merowinger war der Ort besiedelt wie gefundene Keramiken zeigen.
Müllheim gehörte zur Herrschaft Badenweiler ein der Gebiete der alemannischen Herzöge die um das Jahr 500 von den Franken unterworfen wurden.
Um das Jahr 1000 kam die Gegend unter die Herrschaft Zähringer Herzöge. Mit dem Tod von Berchthold von Zähringen starb die Linie der Zähringer aus und Müllheim kam 1218 in den Besitz der Grafen von Der letzte der Freiburger Grafen Johann von trat 1444 die Herrschaft Badenweiler an die Markgrafen Hachberg ab. Markgraf Philipp von Hachberg schloss Markgraf Christoph von Baden im Jahr 1490 einen Erbvertag ab. Nach dem Tod 1503 fielen die Herrschaften Sausenburg Rötteln und an Baden .
Es waren ursprünglich zwei Orte Ober- Untermüllen die zusammenwuchsen als 1727 der Amtssitz Vögte von Badenweiler nach Müllheim verlegt wurde. 1698 erhielt der Ort das Marktrecht . 1810 erhob der badische Großherzog den bisherigen zur Stadt.
Seit 1872 findet alljährlich der Müllheimer Weinmarkt der badische Weinmarkt und Spezialmarkt für Markgräfler Weine
Müllheim ist Sitz eines Amtsgerichtes eines eines Polizeireviers sowie des Staatlichen Forstamtes. Zudem die Stadt eine Außenstelle des Landratsamtes (einschließlich Außenstelle des Gesundheitsamtes und der Kfz-Zulassungsstelle) ein sowie eine Außenstelle Arbeitsamtes und des Staatlichen Freiburg.