W średniowieczu władzę świecką na terenie obecnego Kreuzlingen sprawowali książęta-biskupi pobliskiej Konstancji. Z roku 830 pochodzi pierwsza pisemna wzmianka na temat wsi Kurzrickenbach (Rihinbah), wchodzącej obecnie w skład miasta. W roku 1125 Ulryk I, biskup Konstancji, założył klasztor augustianów w Egelshofen. Od tego klasztoru, zwanego crucelin, pochodzi obecna nazwa miasta. W XV wieku kanton Thurgau, na terenie którego leży Kreuzlingen, przeszedł we władanie Konfederacji Szwajcarskiej.
Obecne centrum miasta jeszcze w początkach XIX wieku było niezabudowane, pokryte łąkami i uprawami. W roku 1818 powstał pierwszy posterunek graniczny. Regularna żegluga na Jeziorze Bodeńskim od 1824 roku oraz budowa linii kolejowej do Romanshornu w 1871 roku przyczyniły się do ożywienia gospodarczego, tak iż w roku 1874 do Kreuzlingen przeniosły się władze administracyjne regionu. Do wybuchu pierwszej wojny światowej miejscowość ta była jednak mocno związana z sąsiednią, jednak leżącą już w Niemczech Konstancją.