Die Siedlung Heidenfeld ist wahrscheinlich während der fränkischen Landnahme in der ersten Hälfte des 8. Jahrhunderts entstanden.Der Name leitet sich vermutlich her von "Feld des Heidino". Ausgangspunkt der Siedlung war wohl die kleine Anhöhe in der Nähe des Mains,auf der später eine Kirche und ein ummauerter Kirchhof errichtet wurden.Sicher vor dem Jahr 855, wahrscheinlich sogar vor 775, gelangte Heidenfeld an das Kloster Holzkirchen, das zu dieser Zeit zur Abtei Fulda gehörte. Von da an bestanden für viele Jahrhunderte enge Verbindungen zwischen Holzkirchen und Marktheidenfeld. Das KlosterHolzkirchen hatte auch umfangreichen Grundbesitz in Heidenfeld und war lange Mitbesitzer des Dorfgerichts. 

Die Wertheimer Grafen, die über das Kloster Holzkirchen die Vogteiausübten, erlangten Ende des 13. Jahrhunderts auch die Vogtei über Heidenfeld, verleibten die Siedlung ihrer Grafschaft ein und bautensie weiter aus. Im Jahr 1397 wird Marktheidenfeld als "oppidum", als Stadt Heidenfeld bezeichnet. Seit der Mitte des 15. Jahrhunderts sind Schultheißen belegt, ein Rathaus lässt sich erstmals im 16. Jahrhundertnachweisen und ebenso die - nahezu städtische - Vierteleinteilung der Gemeinde. Zu den städtischen Rechten hat wohl neben der Ummauerung schon damals das Marktrecht gehört.

Ab 1522 wurde in der Grafschaft Wertheim die Reformation eingeführt. In Heidenfeld lassen sich ab 1530 evangelische Prediger, bald als zuständige Pfarrherren nachweisen. Das 16. Jahrhundert war eine Blütezeit für die Siedlung. Die Bevölkerung stieg in dem schon damals gewerblich geprägten Ort von 530 im Jahr 1542 auf rund 800 gegen Ende des 16. Jahrhunderts. Nachgewiesen ist für diese Zeit auch eine Schule, wahrscheinlich eine Lateinschule.

Nach dem Aussterben der Wertheimer Grafen im Mannesstamm im Jahr 1556 traten Graf Ludwig von Stolberg-Königstein-Rochefort bzw. seine Erben die Nachfolge an. Unklare Rechtsverhältnisse gaben dem Hochstift Würzburg die Möglichkeit, alte Ansprüche geltend zu machen. Im Jahr 1612 wurde Heidenfeld als würzburgisches Lehen eingezogen. Nun setzte die Gegenreformation unter dem Pfarrer Johannes Molitor ein. In dieser Zeit wurde auch die Pfarrkirche St. Laurentius neu gebaut. Und ebenfalls damals bürgerte sich der Name Marktheidenfeld ein, erstmals belegt im Jahr 1649.

Ab 1631 erfasste der Dreißigjährige Krieg den fränkischen Raum; in diesem Zusammenhang wurde Marktheidenfeld von 1632 bis 1634 wieder der Grafschaft Wertheim zugeschlagen. Damit wurde für diesen Zeitraum auch erneut die evangelisch-lutherische Konfession eingeführt. 

Der Krieg verursachte einen gewaltigen Bevölkerungsrückgang. Nur noch rund 500 Einwohner hatte Marktheidenfeld am Ende des Dreißigjährigen Krieges im Jahr 1648. Schultheiß war damals Sebastian Stöber, an den heute noch das Friedhofskreuz von 1624 und sein Grabstein von 1672 erinnern.

Nach 1648 erholte sich die Gemeinde schnell und wurde zunehmend zum gewerblich-wirtschaftlichen Mittelpunkt des Umlandes. Dazu trugen das vielseitige Handwerk und die Jahrmärkte bei, die im 18. Jahrhundert an Walburgis (1. Mai), an Bartholomäi (24. August) und an Katharina (25. November) stattfanden. Ab 1790 veranstaltete man den Sommermarkt am Fest des Kirchenpatrons Laurentius. Ab 1948 entwickelte sich dieser Jahrmarkt zur Laurenzi-Messe, die jährlich in der Woche um den 15. August als großes Volksfest für das ganze Umland gefeiert wird.

In den Jahren 1648 bis 1651 kam es mit dem Mittelpunkt Marktheidenfeld zur Errichtung der Zünfte der Schneider und Krämer, der Fischer und Schiffer, der Schuster und Gerber, der Büttner, Steinhauer, Maurer, Bäcker und zu Beginn des 18. Jahrhunderts der Schmiede, Zimmerer und Wagner. Diese Amtszünfte unterstreichen die überörtliche Bedeutung des Marktes.

Ab der zweiten Hälfte des 17. Jahrhunderts fanden in Marktheidenfeld eine rege Bautätigkeit und die Erweiterung der Siedlung in der Mitteltorstraße und am Mainkai statt. Im Jahr 1720 hatte Marktheidenfeld bereits rund 1.100 Einwohner. In der ersten Hälfte des 18. Jahrhunderts wurde die Pfarrkirche St. Laurentius erweitert, 1745 errichtete der Weinhändler Franz Valentin Franck sein prächtiges smalteblaues Haus in der Untertorstraße, das heute Kulturzentrum der Stadt ist. In seinen Gewölbekellern ist der Überlieferung nach der erste deutsche Sekt hergestellt worden. 1796 folgte als weiterer bedeutender Wirtschaftsfaktor die Gründung der ersten Brauerei. Schiffsbau, Orgelbau und Bildhauerei sind als besondere Gewerbe Ende des 18. Jahrhunderts in Marktheidenfeld nachgewiesen.

1803 wurde das Hochstift Würzburg säkularisiert und Marktheidenfeld dem Kurfürstentum Bayern zugeschlagen. Von 1806 bis 1814 gehörte es zum Großherzogtum Toskana-Würzburg und wurde dann dem Königreich Bayern einverleibt. Im Zusammenhang mit diesen Veränderungen wurde 1806 Marktheidenfeld Sitz des Landgerichts. 1862 wurden Justiz und Verwaltung getrennt. Neben das Landgericht trat das Bezirksamt, das 1939 den Namen Landratsamt erhielt. 1831 wurde als erster Amtsbau das Gefängnis in der Würzburger Straße errichtet. 1835 wurde der Beschluss zum Bau der Mainbrücke in Marktheidenfeld gefasst. Diese Brücke - eine der ältesten und schönsten am bayerischen Main - wurde 1846 dem Verkehr übergeben.

Das erhöhte Verkehrsaufkommen führte zum Abbruch der Stadttore, an die heute nur noch die Straßennamen erinnern: 1845/46 fiel das Obertor, 1860 das Mitteltor und 1863 das Untertor. Errichtet wurde 1865/66 das Rat- und Schulhaus am Marktplatz.

1870/71, zur Zeit des Deutsch-Französischen Krieges, lebten in Marktheidenfeld 1.860 Einwohner. 

Ab 1880 erschien im Amtsstädtchen die Lokalzeitung "Marktheidenfelder Bote";  auch dies war Zeichen der Aufbruchstimmung der Gründerjahre, die mit dem Bau der Eisenbahnstrecke von Lohr nach Wertheim einsetzte. 1881 wurde die Bahnstrecke eröffnet, die Marktheidenfeld an dieses Verkehrsmittel bis in die 1970er Jahre anband. 

1884 wurde ein Krankenhaus in der heutigen Petzoltstraße neu gebaut, 1885 das Forstamt in der Nachbarschaft errichtet, 1887 wurde das repräsentative Amtsgerichtsgebäude in der Würzburger Straße fertiggestellt.

1890 entstand über der Stadt die Kreuzbergkapelle, 1896 die evangelische Kirche. Die katholische Kirche St. Laurentius wurde 1897/98 um die beiden Seitenschiffe erweitert. Durch den Zuzug aus den Umlandgemeinden bildete sich in Marktheidenfeld um 1909 eine jüdische Kultusgemeinde, die bis zu den Verfolgungen während der Gewaltherrschaft des Dritten Reiches bestand.

Mit der Sprengung der Mainbrücke und dem Einmarsch der Amerikaner am 2. April 1945 endete für Marktheidenfeld der Zweite Weltkrieg. 1946 lebten rund 4.300 Menschen in Marktheidenfeld. Viele Heimatvertriebene und Flüchtlinge, hauptsächlich Sudetendeutsche und Schlesier, fanden hier eine neue Heimat.

Ab Ende der 1960er Jahre erfolgte der Zuzug ausländischer Arbeitnehmer aus dem damaligen Jugoslawien, der Türkei, aber auch aus Portugal, Spanien und Italien. In den 1980er- und 90er Jahren kamen Spätaussiedler (Länder der früheren Sowjetunion und Rumänien) nach Marktheidenfeld. Die stetige Ausweisung von Baugebieten sorgte für rege Bautätigkeit, bot Möglichkeiten zur Gründung und Ansiedlung neuer Gewerbe- und Industriebetriebe und für Beschäftigung. Grundlegend veränderte sich die Stadt. Neubaugebiete prägten das Bild, die neue Pfarrkirche St. Josef wurde 1967, ein neues Krankenhaus 1968 eingeweiht. Und ab Ende der 1960er-Jahre wurde Marktheidenfeld zur Schulstadt mit Realschule, Gymnasium, Fachoberschule und Förderschuleinrichtungen.

1972 wurde im Rahmen einer Gebietsreform der Landkreis Marktheidenfeld aufgelöst, die Stadt verlor den Kreissitz und damit auch die damit verbundenen amtlichen Einrichtungen. Zu diesem Zeitpunkt lebten rund 6.600 Menschen in der Stadt.

Eingemeindet wurden im Jahr 1972 Glasofen, 1974 Zimmern, 1975 Marienbrunn und 1976 Altfeld, Michelrieth und Oberwittbach. Damit greift das Stadtgebiet in den Spessart aus und Marktheidenfeld, das in seinem Wappen seit 1883 die Brücke mit dem Stern des Glücks führt, ist zur Brücke zwischen "Wald und Reben" geworden.

Marktheidenfeld, das in den letzten Jahren seine Position als Gewerbe- und Industriestandort weiter ausgebaut hat (Stand 31.12.2020) 11.930 Einwohner.

Der Historische Verein Marktheidenfeld e.V. hat die Geschichte Marktheidenfelds von der ersten urkundlichen Erwähnung bis zum Ende des 2. Weltkrieges in einem Buch dokumentiert. Diese Stadtchronik ist zum Preis von 35,00 Euro an folgenden Stellen erhältlich:

• Touristinformation der Stadt Marktheidenfeld, Marktplatz 22
• Kulturzentrum Franck-Haus, Untertorstraße 6