Název obce pochází od augustiniánského kláštera Crucelin, který byl později přejmenován na opatství Kreuzlingen. Nechal ho postavit v roce 1125 kostnický biskup Ulrich I. Za švábské války a třicetileté války po obléhání Kostnice švédskými vojsky bylo opatství Kreuzlingen vypáleno Kostničany. Ze zločinu byli obviněni mniši, protože podporovali nepřítele. V roce 1650 byl klášter obnoven na svém současném místě. Kvůli sekularizaci v roce 1848 se z budov stala škola. Kaple se stala katolickým kostelem
V oblasti Kreuzlingenu žili lidé již v době bronzové. Keltské a římské mince a artefakty ukazují, že lidé se v oblasti usazovali i v době před vznikem písma. Kurzrickenbach je poprvé zmiňován jako Rihinbah v roce 830, Egelshofen je zmiňován jako Eigolteshoven v roce 1125 a Emmishofen je zmiňován jako Eminshoven v roce 1159. Území obce, s výjimkou augustiniánského kláštera, patřilo kostnickému biskupovi.
Až do začátku 19. století bylo dnešní centrum Kreuzlingenu stále převážně zemědělské. První parníky začaly na Bodamském jezeře jezdit v roce 1824. První vlaková trať do Romanshornu byla dokončena v roce 1871 a druhá do Etzwilenu v roce 1875. To přineslo do oblasti obchod a průmysl. V roce 1874 se hlavním městem okresu stal Kreuzlingen namísto dosavadního Gottliebenu. Až do první světové války však byl Kreuzlingen jakýmsi předměstím Kostnice. Většina jeho zisků připadala německým firmám. Válka Kreuzlingen více osamostatnila.
w:Důležitou roli v historii Kreuzlingenu sehrálo sanatorium Bellevue (1857-1980), které se nacházelo v části starého kláštera. V roce 1842 koupil jistý Ignaz Vanotti z Kostnice rozsáhlý pozemek a v roce 1843 zde postavil budovu pro emigrantský tisk Bellevue, který se předtím nacházel v Römerburgu. V roce 1857 koupil pozemek Ludwig Binswanger, psychiatr z Münsterlingenu, a otevřel zde soukromé sanatorium. Klinika byla velmi moderní a zůstala v režii rodiny Binswangerů téměř 120 let. V sanatoriu byly učiněny významné psychiatrické objevy, zejména pod vedením zakladatelova vnuka, zejména v oblasti rozvoje existenciální psychoterapie. Z jeho budov se však zachovalo jen málo.