Überlingen wurde unter dem Namen "Iburinga" im Jahr 773 erstmals urkundlich erwähnt, und zwar als fränkischer Verwaltungssitz im Zusammenhang mit einer Schenkung an das Kloster St. Gallen. Schon im 7. Jahrhundert hatte in Überlingen aber, wie es scheint, ein alemannischer Herzog namens Gunzo residiert, dessen Tochter durch den hl. Gallus von einem bösen Geist befreit worden war.

Die ältesten Teile des Stadtkerns um Münster und Rathaus bis zum wohlerhaltenen "inneren Ring" der Stadtbefestigung, heute auch durch das gotische Franziskanertor markiert, gehen vermutlich auf die Staufer zurück, vielleicht auf Kaiser Friedrich I. Barbarossa, der Überlingen um 1180 das Marktrecht verlieh. Als Marktort und Hafen am hier nur etwa 3 km breiten Überlinger See, wo zudem etliche Straßen zusammenführten, gewann der Ort rasch an Bedeutung. Die Erhebung zur Stadt erfolge um 1210/20 unter König Friedrich II. Nach dem Aussterben der Staufer 1268 errang Überlingen den Status einer Reichsstadt.

Eine seit 1426 in sieben Zünften organisierte Handwerkerschaft und das Stadtpatriziat lebten auf der Grundlage der wohl schon 1300 geschaffenen Zunftverfassung einträchtig miteinander. Schon früh betrieb die Stadt auf ca. 268 ha der Gemarkung an den sonnigen Südhängen einen intensiven Weinbau. Noch wichtiger für den Export wurde der Handel mit Getreide, das aus dem oberschwäbischen Hinterland auf den Überlinger Markt im Gredhaus transportiert und von dort besonders in die Schweiz verschifft wurde. Bis ins 19. Jahrhundert besaß Überlingen einen der größten Kornmärkte in Süddeutschland.

Die Stadt und ihr reiches Spital brachten immer mehr Land in ihren Besitz, so dass Überlingen am Ausgang des Mittelalters über ein größeres Territorium als manche anderen Reichsstadt verfügte. Ihr schönstes künstlerisches Denkmal schuf sich die Stadt 1490 – 1994 im reich geschnitzten Rathaussaal mit den Darstellungen der Reichsstände von der Hand des Meisters Jakob Russ.

Ein Monument, das zugleich Frömmigkeit und Selbstbewusstsein der Bürgerschaft manifestierte, ist das in den Jahren 1350 – 1562/63 entstandene St. Nikolaus-Münster, der größte spätgotische Kirchenbau des Bodenseegebiets. In seinem Kapellenkranz birgt es durch die Bürger der Stadt gestifteten Altäre von der Gotik bis zum Barock, im Chor den vom Rat in den Auftrag gegebenen, 1613 – 1616 geschaffenen Hochaltar des Meisters Jörg Zürn und seiner Verwandten, eines der bedeutendsten plastischen Kunstwerke seiner Zeit am Bodensee.

Im 30-jährigen Krieg wurde die Stadt durch die Schweden 1632 und 1634 vergeblich bestürmt und belagert, jedoch 1643 durch einen Handstreich von Konrad Widerholt, Kommandeur der Festung Hohentwiel, eingenommen. Mit dem Krieg brach eine Zeit des wirtschaftlichen Niedergangs an. Im Gefolge der napoleonischen Kriege verlor Überlingen wie andere Reichsstädte die Reichsunmittelbarkeit und fiel 1802/03 an Baden.

Als badische Landstadt öffnete sich Überlingen schon im 19. Jahrhundert dem Fremdenverkehr. Damals wurde der alten befestigten Seefront, wovon etwa noch der Turm beim Kursaal am See Zeugnis gibt, eine Uferpromenade vorgelagert, die dann 1971/76 beim Neubau der Kanalisation eine repräsentative Verbreiterung erfuhr. Mit 5 km hat Überlingen eine der längsten Promenaden der Bodenseeorte. Ende des 19. Jahrhunderts war der rasch berühmte Stadtgarten angelegt worden. Es zählt mit Baumbestand, Blumenbeeten und Kakteengruppen neben der Mainau zu den botanischen Sehenswürdigkeiten der Region.

Hatte die Dampfschifffahrt auf dem Bodensee Mitte des 19. Jahrhunderts vor allem den Fremdenverkehr begünstigt, so förderte der Anschluss an das Eisenbahnnetz 1895/1901 die Industrialisierung. Seither stand die Stadt sozusagen "auf zwei Beinen", als Erholungs- und Kurort wie als Sitz mehrerer Gewerbegebiete, die im Osten und Nordosten angesiedelt wurden. 1955 erhielt die Stadt als bisher einzige in Baden-Württemberg das Prädikat eines staatlich anerkannten Kneipp-Heilbades.

Nach wie vor ist Überlingen gleichermaßen Kurgästen wie bei Ruheständlern, zudem als Zweitwohnsitz beliebt. Im Fremdenverkehr steht die Stadt am Bodensee immer noch an vorderer Stelle. Auch dank zahlreicher weiterführender Schulen behauptet sie im Linzgau ihren kulturellen Rang. Im Jahr 2021 wurde in Überlingen die Landesgartenschau ausgerichtet und steigerte dadurch ihre ohnehin schon große Attraktivität für den Fremdenverkehr.

Die Funktion als Kreissitz hat Überlingen 1973 im Zuge der Verwaltungsreformen eingebüßt, doch wurden die bis dahin selbstständigen Gemeinden Bambergen, Bonndorf, Deisendorf, Hödingen, Lippertsreute, Nesselwangen und Nußdorf eingegliedert.

Mit den Gemeinden Sipplingen und Owingen bildet Überlingen seit 1975 eine Verwaltungsgemeinschaft. 1993 wurde Überlingen zur "Großen Kreisstadt" erhoben.

Städtepartnerschaften verbinden Überlingen seit 1987 mit der französischen Stadt Chantilly, 40 km nördlich von Paris, und seit 1990 mit der Stadt Bad Schandau, 40 km östlich von Dresden.