An der St.-Laurentius-Kirche ist seit über 700 Jahren immer wieder gebaut worden. Insgesamt vier Bauabschnitte im romanischen, gotischen, barocken und neubarocken Stil lassen sich unterscheiden. Die Stile der jeweiligen Zeit wurden dabei immer in das alte Bauwerk harmonisch eingebracht. Zu Recht kann man die St. Laurentiuskirche daher als Geschichtsbuch der Stadt bezeichnen.

Echter Kirche
Mit Sicherheit belegt werden kann das Baujahr der "Echter-Kirche" durch eine aus dem Jahr 1613 stammende Gedenktafel, die heute im Innern der ehemaligen Pfarrkirche St. Laurentius angebracht ist. Sie erinnert sowohl an die Wiedereinführung der katholischen Konfession als auch an den Neubau der Kirche in diesem Jahr. Fürstbischof Julius Echter von Mespelbrunn hatte im damaligen Heidenfeld nach dem Rückfall an das Hochstift Würzburg anstelle der alten romanischen Kirche eine neue Kirche, die Echter-Kirche, als sichtbares Zeichen der Gegenreformation errichten lassen. Zuvor war Heidenfeld jahrhundertelang unter der Herrschaft der Grafen von Wertheim; diese hatten in den 1520er Jahren in Heidenfeld die Lehre Martin Luthers verkünden lassen. 
Das Langhaus der alten romanischen Kirche wurde abgebrochen. Nur der Chorraum, das Untergeschoss des Turmes blieb erhalten. Die neue einschiffige Kirche wurde im sogenannten Echter-Stil errichtet, einer Mischform von Spätgotik und Renaissance, mit dem von Ferne sichtbaren Wahrzeichen aller Echter-Kirchen, dem spitzen Turm. Dieser ist jedoch im Jahr 1805 nach einem Blitzschlag abgebrannt und durch den heutigen zwiebelförmigen Turm ersetzt worden.

Fresken im Chorraum der romanischen Kirche
Von dem Vorgängerbau der Echter-Kirche ist nur wenig bekannt. Wahrscheinlich handelte es sich um eine im überschwemmungsfreien Bereich gelegene kleine Wehrkirche, die in Krisenzeiten Zuflucht bieten konnte. Neben dem Chorraum ist noch ein romanisches Doppelfenster an der Nordseite des Turmes erhalten. Anlässlich der Renovierung der St.-Laurentius-Kirche 1982/83 wurden unter dem Innenputz der Sakristei mittelalterliche Fresken gefunden. Diese wurden 2003 teilweise freigelegt. Zum Vorschein kamen eine Abbildung von Christus als Pankrator, als Herrscher über die ganze Welt und den gesamten Kosmos, sowie eine Abbildung der vier Evangelisten, dargestellt als Tier-Symbole. Es wird vermutet, dass die Wandmalereien aus dem frühen 16. Jahrhundert stammen.

Grabplatten von Wilhelm und Elisabeth von Krichingen
Einen weiteren bedeutenden kunsthistorischen Fund gab es ebenfalls im Jahr 2003. Bei den Renovierungsarbeiten wurden auch zwei alte Grabplatten entdeckt, die Wilhelm und Elisabeth von Krichingen (gestorben 1610 bzw. 1612) darstellen. Wilhelm und Elisabeth von Krichingen waren Nachfolger der Wertheimer Grafen, nachdem Graf Michael III. von Wertheim bereits 1556 ohne männliche Nachkommen verstorben war. Die beiden Grabplatten sind inzwischen unter der bereits erwähnten Gedenktafel an den Bau der Echter-Kirche von 1613 aufgestellt worden.

Erweiterung und Umbau im 18. Jahrhundert
In der ersten Hälfte des 18. Jahrhundert wurde das Kirchenschiff verlängert und mit der barocken Schaufassade abgeschlossen. Es folgte eine Umgestaltung im Innern des Gotteshauses. Ein Hochaltar und ein Altarbild zu Ehren des Kirchenpatrons Laurentius wurden angefertigt. Letzteres stammt von Georg Sebastian Urlaub aus Thüngersheim bei Würzburg.

St. Laurentius, Diakon des Papstes Sixtus II., starb den Märtyrertod. Der Legende nach wurde er auf einem Rost gemartert, weil er sich weigerte, die ihm anvertrauten Schätze der Kirche herauszugeben. Eine Statue des Heiligen Laurentius ziert die Schaufassade des Gotteshauses zur Obertorstraße. Eine weitere findet sich in der Kirche; in der Hand hält Laurentius als Erkennungszeichen den Rost. Die das Altarbild einschließenden Statuen von Petrus und Paulus hat Jakob van der Auvera geschaffen, dessen Sohn Johann Wolfgang der bedeutendste Bildhauer der Würzburger Residenz gewesen ist. 
 
Verbunden mit der starken Bevölkerungszunahme der Marktgemeinde Marktheidenfeld am Ende des 19. Jahrhunderts wurde die Kirche schließlich 1897/98 um die beiden Seitenschiffe erweitert. Ende der 1960er Jahre wurde als zweite katholische Kirche die Pfarrkirche St.Josef erbaut.

Renovierung 1982/83 und Umgestaltung des Kirchenumgriffs 2002/03
In den Jahren 1982/83 wurde die St.-Laurentius-Kirche renoviert. Die Treppenlage zwischen Chor und Kirchenschiff wurde geändert und der neue Volksaltar, der Ambo und die Priestersitze aus heimischem roten Sandstein gefertigt. Im Rahmen der Altstadtsanierung wurde 2002/03 der Kirchenumgriff neu gestaltet. Die Idee war, die Kirche als Baukörper erlebbar zu machen und sozusagen die Kirche "in die Stadt zu stellen". Sämtliche Einbauten im Umgriff der Kirche wurden im Zuge der Sanierungsmaßnahme beseitigt und die Treppenanlagen umgebaut. Entstanden ist eine offen und einladend wirkende Freifläche, die sich über drei Ebenen erstreckt und zum Verweilen einlädt.

Laurenzi-Messe
Der Kirchenpatron St. Laurentius gab auch dem größten Volksfest in Marktheidenfeld seinen Namen. Alljährlich um den Feiertag Maria Himmelfahrt (15. August) herum feiert Marktheidenfeld neun Tage lang mit Gästen aus Nah und Fern die Laurenzi-Messe.