Herbsheim est mentionné pour la première fois en 1136 sous le nom de Nerbolsheim dans les archives de 1'abhave de Shuttern (Pays de Bade) qui  y possédait des biens. Cependant, il  semble que le site, traveïsé par le chemin celte Ettenheim - Andlau, ait déjà été occupé il y a fort longtemps. Les nombreux tumuli - au nombre de 62 éparpillés sur les bans de Herbsheim et de Obenheim - semblent confirmer cette hypothèse.

Certains de ces tumuli ont été fouillés au siècle dernier, notamment en 1864 par N. Nickles, apothicaire de Benfeld - et plus récemment, en 1987, par les chercheurs rattachés au musée d'Archéologie de Strasbourg (fouille de sauvetage au lieu dit "Vier Tagen" avant le remembrement). Un squelette datant d'environ 500 ans avant Jésus-Christ, a été découvert dans ce tumulus qui servait de site funéraire à une peuplade celte qui vivait dans cette région à l'époque de la Tène-Halstatt. On y a également trouvé des objets habituels (bracelet en métal, fragments de poterie) et une fibule en ambre. Cette découverte prouverait que ces peuplades commerçaient avec les régions maritimes du nord de l'Europe, puisque l'ambre est une résine fossile dure provenant de mammifères marins, comme le cachalot.

Au Moyen Age, Herbsheim appartenait à. 1'évêque de Strasbourg. Un château s'élevait au sud-est du village. A cet endroit on peut encore observer les vestiges d'un fossé qui entourait probablement l'édifice. Dans le mur extérieur de la nef de l'église paroissiale est incrusté une pièce en grés qui proviendrait des ruines du château et qui représente le blason du village. Ce dernier, fief des landgraves von Werd, revint à l'évêque de Strasbourg en 1359. Le nom du village a changé au cours des siècles. De Nerbosheim ou Herbonsheim en 1136, Herbotesheim en 1244, il est devenu Herbsheim, certainement en raison de son diminutif  Herbse.

La population, principalement paysanne jusqu'en 1945, est passée de 362 habitants en 1851, 580 habitants en 1900, 635 habitants en 1982 à environ 750 de nos jours. En plus des cultures traditionnelles, on exploitait des plantations de houblon jusque vers 1930. Un séchoir existait jusqu'en 1945. On plantait également du lin (Flachs) et du chanvre (Hanf). Le ruisseau Hanfgraben, qui longe la forêt du Mayli et le village, a certainement été nommé ainsi pour l'utilisation qu'on en faisait : tremper les tiges pour en déparer les fibres qui donnaient la filasse (rouissage). Herbsheim possédait également son moulin à huile. On y fait déja allusion dans les archives communales vers 1736. L'engin était actionné par un cheval qui entraînait la grosse meule jusque vers 1920. Par la suite un moteur électrique a pris le relais. Les cultivateurs du village et des environs venaient y faire broyer leur récolte de colza et de noix. La précieuse huile obtenue servait d'huile de table pour la famille pour toute l'année.

Le village a beaucoup souffert pendant la deuxième guerre mondiale. Il a été détruit à 80 % lors de l'offensive des alliés en novembre 1944 et de la contre - offensive allemande en janvier 1945. La population a du s'exiler de l'autre côté de 1'Ill pendant plusieurs semaines.

Reconstruites à l'aide des dommages de guerre, les habitations récentes donnent au village un caractère jeune, même s'il a perdu son cachet typiquement alsacien, la plupart des maisons à colombages ayant disparu. La localité a évolué ces dernières années. Les exploitations agricoles se comptent sur les doigts d'une main et les actifs travaillent dans les industries et services du canton, en Allemagne, et un grand nombre fait le déplacement jusqu'à l'agglomération strasbourgeoise. Beaucoup de jeunes continuent à s'instalIer dans le village et y fondent leur famille, preuve que Herbsheim est un village où il fait bon vivre.