Zum ersten Mal wird der Ort 747 als Besitz des Klosters Münster erwähnt (Quelle: Regnum Francorum online RegAls 160). 801 finden wir hier "in Haidulfushaim" auch Besitz des Klosters Fulda (Quelle: CDF 171). Nach der französischen Geschichtsschreibung findet sich der Ort 1120 im "Cartulaire de Hugshoffen" und wird 1361 von Rudolf von Habsburg an seine Vasallen verliehen, die sich "von Rathsamhausen" nannten. Von 1871 bis zum Ende des Ersten Weltkrieges gehörte Heidolsheim als Teil des Reichslandes Elsaß-Lothringen zum Deutschen Reich und war dem Kreis Schlettstadt im Bezirk Unterelsaß zugeordnet.
Der Prediger Jakob Ammann lebte von 1693 bis 1695 in Heidolsheim; die 1973 geborene, spätere Fußballnationalspielerin Sandrine Ringler verbrachte ihre gesamte Jugend dort.
Literatur
Le Patrimoine des Communes du Bas-Rhin. Flohic Editions, Band 1, Charenton-le-Pont 1999, ISBN 2-84234-055-8, S. 592–593.