Lange vor dem Erzstift Mainz scheint Besitzer von Külsheim das Hochstift Würzburg gewesen zu sein, dessen Ministeriale Oddo von Cullesheim 1144 genannt wird.
Auf eine viel frühere fränkische Gründung weist das Martinspatrozinium der Kirche zu Külsheim hin, das es mit anderen schon im 8. Jahrhundert nachweisbaren Orten des Taubergaus gemein hat.
Erbauer der auf dem höchsten Punkt neben der Kirche gelegenen Burg, deren Bergfried aus dem 13. Jahrhundert erhalten ist, waren wohl die Edelherren von Dürn.
1225 wird das Dorf Külsheim erstmals als Eigentum des Mainzer Erzbischofs Siegfried III. von Eppstein bezeichnet, dem das Erzstift auch sonst wichtige Erwerbungen in Nordbaden verdankt.
1292 verlieh König Adolf Külsheim das Recht der Stadt Frankfurt am Main. 1291 erwarben die Grafen von Wertheim das Pfandrecht über Dorf und Schloss Külsheims, mussten es zwar schon im folgenden Jahr wieder an Mainz zurückgeben, konnten aber im 14. und Anfang des 15. Jahrhunderts erneut in den Pfandbesitz über Külsheim gelangen.
In der Külsheimer Fehde wurde die Stadt 1462 durch den papsttreuen Graf Johann III. von Wertheim nach kurzer Belagerung erobert und der Mainzer Pfandschaftsinhaber Anton von Wittstadt vertrieben. Auf pfalzgräflichen Schiedsspruch hin musste Graf Johann 1480 die Stadt jedoch wieder an das Erzstift abtreten.
Im Bauernkrieg trat Külsheim mit den übrigen Mitgliedern des Mainzer Neunstädtebundes auf die Seite der Aufständischen und wurde von Mainz mit dem Entzug seiner freiheitlichen Stadtverfassung bestraft.
Die im 14. und 15. Jahrhundert meist verpfändete Stadt wurde 1536 Kellereiort und Sitz eines Mainzer Centgrafen, der im Schloss wohnte. 1803-06 gehörte Külsheim zum Fürstentum Leiningen.
Am 23.07.1866 kam es bei Hundheim nordwestlich von Külsheim zu einem Gefecht zwischen badischen und preußischen Truppen (Tauberbischofsheim).
Nach Külsheim eingemeindet wurden 1971 Eiersheim und Hundheim, 1972 Uissigheim, 1975 Steinbach und Steinfurt.
Die Hauptgebäude der Burg stammen in ihrer jetzigen Gestalt mit Ausnahme des Mitte 13. Jahrhunderts erbauten Bergfrieds aus der 2. Hälfte des 16. Jahrhunderts (Südbau) und aus dem Anfang des 17. Jahrhunderts (Ostbau). Sie wurde 1842 von der Stadt erworben und diente seit 1872 als Schule. - Die zwischen 1471 und 1497 errichtete, im 18. und 19. Jahrhundert innen und außen umgestaltete Stadtkirche enthält in den untersten Geschossen des Turmes noch Reste der Vorgängerin aus dem 13. Jahrhundert, die 1470 durch einen Brand vernichtet wurde.
Zwei leuchtertragende Engel von Tilmann Riemenschneider aus der Kirche zu Külsheim befinden sich heute im South-Kensington Museum in London. - Vermutlich an der Stelle der ältesten Martinskirche wurde 1439-44 die spätgotischen Katharinenkapelle erstellt. An der Westseite des Kirchplatzes stehen zwei alte Zehntscheuern, eine von 1499 mit dem Wappen des Erzbischofs Berthold von Henneberg, die anderen von 1624.
Das Rathaus, ein großer, freistehender Bau mit massivem Untergeschoss und einem Fachwerkoberbau von 1522, hat an der gleichen Stellen schon einen Vorgänger besessen. Mehrere Herrenhöfe (Templerhaus, Baumannshaus) und Bürgerhäuser aus dem 16. Jahrhundert sind ebenfalls noch gut erhalten. Der Kapellenbrunnen stammt aus dem 14. Jahrhundert.