Le nom de la municipalité provient du monastère augustinien de Crucelin, qui a ensuite été rebaptisé Abbaye de Kreuzlingen. Il a été construit en 1125 par l'évêque de Constance, Ulrich I. Pendant la guerre de Souabe et la guerre de 30 ans qui a suivi le siège de Constance par les troupes suédoises, l'abbaye de Kreuzlingen a été brûlée par les habitants de Constance. Le crime a été imputé aux moines pour avoir soutenu l'ennemi. En 1650, le monastère a été reconstruit à son emplacement actuel. En raison de la sécularisation en 1848, les bâtiments sont devenus une école. La chapelle est devenue une église catholique.
Les gens vivaient déjà dans la région de Kreuzlingen à l'âge du bronze. Des pièces de monnaie et des artefacts celtes et romains montrent que les gens ont continué à être installés dans la région avant l'écriture. Kurzrickenbach est mentionné pour la première fois comme Rihinbah en 830, Egelshofen est mentionné comme Eigolteshoven en 1125, et Emmishofen est mentionné comme Eminshoven en 1159. Le territoire de la municipalité, à l'exception du monastère augustinien, appartenait à l'évêque de Constance.
Jusqu'au début du XIXe siècle, le centre actuel de Kreuzlingen était encore largement agricole. Les premiers bateaux à vapeur ont commencé à naviguer sur le lac de Constance en 1824. La première ligne de chemin de fer vers Romanshorn a été achevée en 1871, et la deuxième vers Etzwilen en 1875. Le commerce et l'industrie s'installent alors dans la région. En 1874, Kreuzlingen devient la capitale du district, à la place de l'ancienne capitale, Gottlieben. Cependant, jusqu'à la Première Guerre mondiale, Kreuzlingen était une sorte de banlieue de Constance. La plupart de ses bénéfices étaient destinés aux entreprises allemandes. La guerre a rendu Kreuzlingen plus indépendante.
w:Le Sanatorium de Bellevue (1857-1980), qui occupait une partie de l'ancien monastère, a joué un rôle important dans l'histoire de Kreuzlingen. En 1842, un certain Ignaz Vanotti de Constance acheta un grand terrain et construisit un bâtiment pour abriter la presse d'émigrants de Bellevue en 1843, qui était auparavant située à Römerburg. En 1857, Ludwig Binswanger, un psychiatre de Münsterlingen, achète la propriété et ouvre un sanatorium privé. La clinique était très moderne et resta sous le contrôle de la famille Binswanger pendant près de 120 ans. D'importantes découvertes psychiatriques, notamment sous le contrôle du petit-fils du fondateur, en particulier dans le développement de la psychothérapie existentielle, ont été faites au sanatorium. Cependant, il ne reste que peu de ses bâtiments.