Le site, fertile et bordé par la Lauch, est occupé depuis la préhistoire. Gundolsheim est mentionné en 728, sous la dénomination "Cundolteshaim" comme dépendance des ducs d'Alsace. De nombreux établissements religieux y possèdent des biens. Le village relève du Haut-Mundat des princes-évêques de Strasbourg, et la collégiale de Lautenbach y détient une cour colongère depuis le XIIème siècle. Les nobles de Gundolsheim construisent leur château à proximité de l'église tandis que les seigneurs de Heidwiller établissent leur manoir sur les bords de la rivière. Les deux châteaux, ainsi que les remparts du village, ont disparu.
En 1465, Gundolsheim devient le point de ralliement des troupes levées en Alsace pour combattre l'armée de Charles le Téméraire. Pendant la guerre de Trente Ans, la population abandonne le village et se réfugie à Rouffach. En 1791, les habitants s'opposent au prêtre constitutionnel installé avec l'intervention de l'armée. Deux ans plus tard, le village subit les assauts des habitants du Florival en raison du refus des paysans de Gundolsheim de livrer leurs céréales au marché de Guebwiller, de peur d'être payés en assignats, ils refusaient de fournir le marché de Guebwiller en céréales. L'armée appelée en renfort empêche de justesse le massacre des villageois.
La guerre de 1870 épargna le village, de même que le premier conflit mondial de 1914-1918. Gundolsheim fut occupé par les Allemands à partir de 1940 et libéré le 5 février 1945, le jour de la Sainte Agathe, patronne du village.
