Anfang der 1980er-Jahre in der Martinskirche durchgeführte Ausgrabungen belegen, dass bereits die Römer in Müllheim gesiedelt haben. Die Kirche wurde auf Mauerresten eines römischen Gebäudes errichtet. Auch zur Zeit der Merowinger war der Ort besiedelt, wie gefundene Keramiken zeigen.
Müllheim gehörte zur Herrschaft Badenweiler, ein Bestandteil der Gebiete der alemannischen Herzöge, die um das Jahr 500 von den Franken unterworfen wurden.
Der Ort wurde erstmals in einer Schenkungsurkunde, datiert vom 27. Oktober 758, des Strachfried an das Kloster St. Gallen als villa mulinhaim erwähnt.
Um das Jahr 1000 kam die Gegend unter die Herrschaft der Zähringer Herzöge. Mit dem Tod von Berchthold V. von Zähringen starb die Linie der Zähringer Herzöge aus und Müllheim kam 1218 in den Besitz der Grafen von Freiburg. Der letzte der Freiburger Grafen, Johann von Freiburg, trat 1444 die Herrschaft Badenweiler an die Markgrafen von Hachberg ab. Markgraf Philipp von Hachberg schloss mit Markgraf Christoph von Baden im Jahr 1490 einen Erbvertag ab. Nach dem Tod Philipps 1503 fielen die Herrschaften Sausenburg, Rötteln und Badenweiler an Baden.
Es waren ursprünglich zwei Orte, Ober- und Untermüllen, die zusammenwuchsen, als 1727 der Amtssitz der Vögte von Badenweiler nach Müllheim verlegt wurde.
Bereits 1698 erhielt der Ort das Marktrecht. 1810 erhob der badische Großherzog den bisherigen Marktflecken zur Stadt.
Seit 1872 findet alljährlich der Müllheimer Weinmarkt, der älteste badische Weinmarkt und Spezialmarkt für Markgräfler Weine statt.
Ortsteile sind neben dem Kernort Müllheim die Dörfer Britzingen, Dattingen, Feldberg, Hügelheim, Niederweiler, Vögisheim und Zunzingen.
