Le nom de Leutenheim est mentionné pour la première fois sous le règne de Charlemagne, dans une charte de donation en faveur de l’abbaye de Wissembourg, le 31 décembre 773. Le nom « Lithaim », d’origine celte, signifie « situé près d’une colline », selon toute vraisemblance celle du Heidenberg, butte qui protégeait les habitants de l’âge de fer au début du Moyen Âge des crues du Rhin et des invasions.
Le hameau de Koenigsbruck doit son origine à l’abbaye cistercienne éponyme fondée au XIIe siècle. Il est rattaché à la commune de Leutenheim en 1790, après la disparition de l’abbaye sous la Révolution française.
Dans l’intervalle, l’Alsace a quitté l’orbite du Saint Empire Romain Germanique pour la domination française. Le traité de Westphalie, signé le 14 octobre 1648, met un terme à la sanglante Guerre de Trente Ans (1618-1648) et ouvre la parfois brutale transition entre souveraineté habsbourgeoise et souveraineté française. Leutenheim, comme de nombreuses communes du Nord de l’Alsace, doit reconnaître la souveraineté du roi de France en 1680. Louis XIV est ainsi le premier roi de France a régné en Alsace.
Le XVIIIe siècle permet à la population alsacienne de se remettre lentement des années de guerre et de disette du siècle précédent. La population de Leutenheim passe ainsi de quelques 160 habitants en 1714, à la fin du règne du Roi Soleil, à 534 personnes en 1790. C’est la Révolution française, comme l’a souligné l’historien Marc Bloch, qui rattache définitivement l’Alsace à la France. Des municipalités élues sont mises en place à la suite d’une loi du15 décembre 1789. Jean Hochnedel illustre la continuité de la gestion des affaires municipales : ancien « prévôt » du village, depuis 1772, il devient le premier maire de la commune de Leutenheim. L’entrée en vigueur de la Constitution civile du clergé en 1790 entraine le rattachement de l’abbaye de Koenigsbruck à la commune.
La Révolution heurte cepandant les convictions de nombreux catholiques et la politique de la Terreur inquiète : près d’une cinquantaine d’habitants de Leutenheim émigrent, profitant de la proximité de la frontière pour trouver refuge en Bade. Le retour à l’ordre imposé par Bonaparte, qui met un terme à l’expérience révolutionnaire, rassure de nombreux Alsaciens. L’empereur est très populaire, notamment grâce à ses campagnes militaires qui mettent pourtant l’Europe à feu et à sang. Les guerres napoléoniennes contribuent en outre à cimenter l’identité nationale allemande, ce qui n’est pas sans conséquence pour notre région et pour notre village.
La guerre franco prussienne de 1870-1871 inaugure un long cycle de conflits au cours desquels l’Alsace est ballottée entre la France et l’Allemagne au gré des rapports de force. A la suite du traité de Francfort, la IIIe République naissante abandonne l’Alsace au II. Reich, premier Etat national allemand. Cette période trop peu connue est marquée par un réel dynamisme économique en Alsace, visible notamment à Strasbourg, dont le pouvoir prussien veut faire une vitrine. Alors que l’Alsace se fait lentement à la domination allemande tout en nourrissant une nostalgie pour la République française, la Première Guerre mondiale éclate. 22 jeunes habitants de Leutenheim périssent dans le conflit sous les couleurs Feldgrau sur différents théâtres d’opération : en Russie, sur la Somme, à Verdun. Si les combats épargnent en grande partie le sol alsacien, la présence d’une poignée de prisonniers de guerre russes à Leutenheim et un combat aérien en août 1918 au dessus du village rappellent à tous la triste réalité de la guerre.
L’armistice signé le 11novembre 1918 marque le retour de l’Alsace sous l’administration française. Un registre est tenu pour notifier la réintégration des Alsaciens dans la nationalité française. Ceux qui sont nés en Alsace, mais dont les parents sont originaires d’Allemagne ou d’Autriche sont considérés comme indésirables et sont chassés du pays. Le retour des soldats dans leur foyer ravive néanmoins l’économie locale. L’agriculture reste une activité importante et encore très peu mécanisée dans l’entre-deux-guerres à Leutenheim. De nombreux habitants exercent souvent un métier artisanal ou tiennent un commerce en plus du travail de la terre : le village compte cinq « Kneipe » ou débits de boissons, quatre épiceries, deux boulangeries, une boucherie, deux huileries, un forgeron, un charron, un tonnelier, deux sabotiers, deux cordonniers, deux menuisiers, trois maçons, deux coiffeurs, deux tailleurs, un bouilleur de cru, quelques couturières, une repasseuse modiste, sans oublier un gardien de porcs et une gardienne d’oies, deux figures du folklore local.
La construction de la ligne Maginot contribue aussi à l’animation du village. L’histoire locale est à nouveau marquée par la situation de région frontière de l’Alsace. Le Ministre de la Guerre et ancien combattant de la Grande Guerre André Maginot veut réaliser une ceinture de fortifications le long des frontières Nord et Est du pays. Leutenheim est directement concerné, se situant dans une position stratégique entre Schoenenbourg et Fort-Louis. Les abris et casemates autour de Leutenheim ont été construit de 1930 à 1933. L’abri de surface du Heidenbuckel est ouvert au public depuis 1995 grâce à l’action des bénévoles de l’association des Amis du Heidenbuckel. Le déclenchement de la Seconde Guerre mondiale le 1er septembre 1939 se traduit pour les habitants de Leutenheim par l’ordre d’évacuation, chaque personne pouvant emporter 30 kilogrammes de bagages. C’est la commune d’Isle, commune de Haute-Vienne située au Sud de Limoges, qui accueille la population de Leutenheim. Quelques habitants de Leutenheim voient le jour dans les confins du Massif Central. Mais le quotidien est difficile pour de nombreux Alsaciens. Après la défaite éclair de l’armée française en mai-juin 1940, Hitler va annexer l’Alsace au IIIe Reich. L’enrôlement dans le Reichsarbeitsdienst puis l’incorporation de force des Alsaciens, Lorrains et Luxembourgeois en août 1942 marque le destin de ces régions. C’est pour eux le terrible front de l’Est, et le goulag, dont le notoirement célèbre Tambov, pour ceux qui sont fait prisonniers par les Soviétiques. 30 habitants de Leutenheim sont ainsi tombés sous l’uniforme allemand, deux sous l’uniforme français, et un habitant de Koenigsbruck a été victime d’une mine, le 1er avril 1945, en rentrant de la messe paroissiale.
Le début de l’année 1945 est marqué par des offensives allemandes et américaines dans notre secteur. L’abri du Heidenbuckel, qui n’a pas connu l’épreuve du feu, sert de refuge aux civils qui cherchent à échapper au combat.
La fin de la guerre marque le début de la réconciliation franco-allemande et de la construction européenne. L’Alsace, longtemps région frontière, redevient un espace transfrontalier marqué par les échanges de biens, de services, de capitaux et de personnes. Près de la moitié de la population active de Leutenheim travaille ainsi en Allemagne, principalement dans le Pays de Bade. Nombreux sont les touristes allemands à fréquenter les restaurants des environs et à visiter l’abri du Heidenbuckel.
Les différentes municipalités qui se succèdent contribuent à développer le village et à améliorer le cadre de vie de ses habitants. Leutenheim adhère également dès 1968 à une logique de coopération intercommunale en s’associant aux communes voisines pour créer le SIVOM de Roeschwoog et environs qui deviendra en 1992, l’actuelle Communauté des Communes de l’Uffried.
La dynamique de coopération se traduit aussi, dans le cadre de la construction européenne, par la création d’Eurodistricts : Leutenheim appartient à la Regio Pamina, lancée en 1988 à la suite de la « Déclaration de Wissembourg », et qui rassemble le Sud du Palatinat, le Mittlerer Oberrhein et le Nord de l’Alsace.