Zwischen 1727 und 1730 ließ der Veitshöchheimer Jude Schmul Moses eine Synagoge in der heutigen Mühlgasse, damals am Rand der Ortsbebauung, errichten. Das Grundstück stellte das Kloster Oberzell zur Verfügung, an das auch die Abgaben hierfür entrichtet werden mussten.

Die äußere Bauform entspricht der im 18. Jahrhundert üblichen dörflichen Wohnhausarchitektur. Das Innere birgt den tonnenüberwölbten Betsaal, eine Wohnung für den Vorsänger und eine Mikwe.

Den Betsaal schenkte der Erbauer bereits 1746 der jüdischen Gemeinde von Veitshöchheim, die 1826 dann noch die Vorsingerwohnung und das Ritualbad von den Erben des Schmul erwarb. Über 200 Jahre lang diente die Synagoge als jüdisches Gotteshaus.

Im August 1938 wurde dann die Übernahme der Synagoge durch die politische Gemeinde von Veitshöchheim in die Wege geleitet. Für den errechneten Abbruchwert des Gebäudes in Höhe von etwa 200 Reichsmark sollte die nur noch wenige Mitglieder zählende jüdische Gemeinde die Synagoge verkaufen. Es blieb den Veitshöchheimer Juden auch keine Wahl, und so wechselte die Synagoge den Besitzer. Dieser Verkauf wurde am 12. November 1938 notariell beurkundet. In der Pogromnacht vom 9. November 1938 war die Synagoge bereits nicht mehr in jüdischem Besitz und wurde deshalb, und weil seit 1926 eine nichtjüdische Familie in der Vorsingerwohnung wohnte, in der betreffenden Nacht von Polizisten bewacht und nicht zerstört. Auch fürchtete man, dass im Falles eines Synagogenbrandes die Nachbarhäuser Schaden nehmen könnten. Tatsächlich plante die Gemeinde Veitshöchheim jedoch, die Synagoge zukünftig als Feuerwehrhaus zu nutzen und achtete auch deshalb darauf, dass diese nicht zerstört wurde.

1940 erfolgte der Umbau zum Feuerwehrhaus. Man entfernte den Eingangsvorbau und brach in West- und Ostwand je ein Rundbogentor. Die Frauenempore wurde abgebrochen, Lesekanzel und Toraschrein zerschlagen und die Bruchstücke als Füllmaterial für den Boden, der auf Straßenhöhe angehoben werden musste, verwendet. Die Wände wurden weiß getüncht und zum Trocknen der Feuerwehrschläuche brach man ein Loch in das Tonnengewölbe. Da der Verkauf im Jahr 1938 nicht den eigentlichen Wert des Grundstücks und des Gebäudes berücksichtigte, zahlte die Gemeinde Veitshöchheim 1950 eine entsprechende Ausgleichzahlung an die Jewish Restitution Successor Organisation (IRSO) und ist seither auch rechtmäßiger Besitzer. Bis etwa 1964 wurde der ehemalige Kultraum der Synagoge als Feuerwehrgerätehaus genutzt. Danach diente er als Lagerraum für den gemeindlichen Bauhof.

Zu Beginn der achtziger Jahre faßte die Gemeinde den Entschluß, das mittlerweile leerstehende Haus in ein Galerie- und Ausstellungsgebäude umzugestalten. Eine Tafel an der Fassade sollte auf die frühere Funktion als Synagoge hinweisen. Bei Beginn der Bauarbeiten 1986 entdeckte man im Füllmaterial des Fußbodens Reste der alten Ausstattung. Diese wurden verwendet, um die ursprüngliche Einrichtung des Betsaal wiederherzustellen. Die Arbeiten dauerten bis zum März 1994, als die Synagoge neu eingeweiht und für kultfähig erklärt wurde. Heute können in der Veitshöchheimer Synagoge wieder Gottesdienste gefeiert werden.