La première trace écrite du nom du village se situant sur le ban actuel, date de l’an 788, et est : HUNZOLFESHEIM.
On le retrouve en 1051 orthographié : AVELSHEIM, puis en 1350 : AFELSHEIM d’ où sa forme dialectale : ÂFELSE. En 1496 on l’écrivait :AFELTZHEIM et en 1589 à nouveau : AVELSSHEIM, mais avec 2 "S"
Depuis lors le village porte son nom actuel et son orthographe n’a plus évolué : Avolsheim est située sur la voie gallo-romaine reliant Molsheim à Saverne ; de nombreux objets datés de cette période y ont été mis au jour en 1930.
La localité aurait été composée au Xe s. de deux hameaux distincts : AVELSHEIM d’une part, correspondant grosso-modo au village actuel et TUMPFIETER", "DOMPIETER" ou "DUMPHIETENHEIM" d’autre part, un bourg constitué d’un groupe de quelques fermes et d’un moulin situés auprès d’une église : le DOMPETER.
Les dernières mentions de ce hameau datent du XVIe s. Il a probablement disparu en tant que village avec la fin de ce même siècle. Pour certains historiens un doute subsiste : ils situent sa disparition au XVIIe s, sa destruction faisant suite au siège de Dachstein par les armées de Turenne.
Selon la bulle du Pape Léon IX , en 1051, Avolsheim dont l’abbaye de Hohenbourg était propriétaire, faisait partie des possessions de l’évêché de Strasbourg .
Elle fut mise en vasselage aux comtes d’Ostoffen, puis aux von Murnhart en 1384, enfin resta aux von Beger jusqu’en 1521.
Depuis 1534 et jusqu’à la Révolution, la localité fut le fief des hauts dignitaires de l’évêché.
Depuis la Révolution, le village est rattaché à la sous-préfecture de Molsheim.