Kommunens namn kommer från augustinerklostret Crucelin, som senare döptes om till Kreuzlingen Abbey. Det byggdes 1125 av biskopen av Konstanz, Ulrich I. Under det schwabiska kriget och det 30-åriga kriget, efter att Konstanz belägrats av svenska trupper, brändes Kreuzlingen-klostret ner av folket i Konstanz. Brottet skylldes på munkarna för att de hade stött fienden. År 1650 återuppbyggdes klostret på sin nuvarande plats. På grund av sekulariseringen 1848 blev byggnaderna en skola. Kapellet blev en katolsk kyrka
Redan under bronsåldern bodde människor i Kreuzlingenområdet. Keltiska och romerska mynt och artefakter visar att människor fortsatte att bosätta sig i området före skrivandet. Kurzrickenbach nämns första gången som Rihinbah år 830, Egelshofen nämns som Eigolteshoven år 1125 och Emmishofen nämns som Eminshoven år 1159. Kommunens territorium, med undantag för augustinerklostret, tillhörde biskopen av Konstanz.
Fram till början av 1800-talet var Kreuzlingens nuvarande centrum fortfarande till stor del en jordbruksbygd. De första ångbåtarna började trafikera Bodensjön 1824. Den första tåglinjen till Romanshorn blev klar 1871 och den andra till Etzwilen 1875. Detta förde handel och industri till området. År 1874 blev Kreuzlingen distriktets huvudstad i stället för den tidigare huvudstaden Gottlieben. Fram till första världskriget var Kreuzlingen dock en slags förort till Constance. De flesta av dess vinster gick till tyska företag. Kriget gjorde Kreuzlingen mer oberoende.
w:Sanatoriet Bellevue (1857-1980), som låg i en del av det gamla klostret, spelade en viktig roll i Kreuzlingens historia. År 1842 köpte en man vid namn Ignaz Vanotti från Constance ett stort markområde och uppförde 1843 en byggnad för att inrymma emigrantpressen Bellevue, som tidigare hade funnits i Römerburg. År 1857 köpte Ludwig Binswanger, en psykiater från Münsterlingen, fastigheten och öppnade ett privat sanatorium. Kliniken var mycket modern och förblev i familjen Binswangers ägo i nästan 120 år. På sanatoriet gjordes viktiga psykiatriska upptäckter, särskilt under grundarens sonsons kontroll, framför allt inom utvecklingen av den existentiella psykoterapin. Få av dess byggnader finns dock kvar.