Fondé entre 693 et 710, le village d'Andolsheim est mentionné pour la première fois en 767 sous le nom d'Ansulfisheim. Il tient son nom d'Ansoal, abbé de Munster, qui devint plus tard évêque de Strasbourg.
Le 17 juin 764, Waldrade remet à son frère l'abbé Fulrad la villa d'Ansulsisheim que celui-ci rattache au prieuré de Lièpvre qu'il vient de fonder.
Le village est environné de riches terres alluviales. En 870, l'Alsace passe sous le contrôle du roi de Germanie par le traité de Meerssen conclu entre Charles le Chauve et Louis le Germanique, et devient ainsi le centre de la civilisation rhénane. Au XIIe siècle, la région d'Andolsheim échappe à la domination des Habsbourg en devenant la propriété des seigneurs de Horbourg. Sigefroi d'Andolsheim paraît en 1187, comme témoin d'une donation du comte Louis de Ferrette en faveur de l'abbaye de Pairis. Au XIIIe siècle, la moitié du village dépend du Mundat de Rouffach.
La bourgade change de main en 1324 et passe aux comtes de Wurtemberg, puissante famille issue du duché de Souabe en 1135 et qui règne sur les terres du sud-ouest de l'Allemagne. Les ducs en 1495, embrassent la Réforme qui à partir de 1535 gagne peu à peu une population de tradition catholique à la religion protestante. En 1648, Louis XIV s'empare des terres des Habsbourg par les traités de Westphalie mais le comté de Horbourg, indépendant, en reste exclu. Ce n'est que partie remise puisqu'en 1678, Louis XIV décide par le traité de Nimègue d'accentuer la politique de réunion de l'Alsace à la France, et en 1680, un arrêt rattache Andolsheim à la couronne de la France. Les intendants du roi ont alors le souci de restaurer la religion catholique. Ils prononcent le simultaneum en 1687. L'église d'Andolsheim est désormais consacrée au culte catholique et au culte protestant.