A zenekart 1992-ben alapította Veszprém városában Kecskeméti Róbert énekes, Bóta Balázs gitáros, Czipri Tibor gitáros, Jutasi Sándor basszusgitáros, Kajtár Péter dobos. Egy évvel az alakulás után elkészült az első demó (Any Problems?). Az 1994-es évet az Akela előzenekaraként kezdte az együttes, majd a Sing Sing koncertjein melegítették be a közönséget, ami nagy lökést adott a népszerűségüknek. A turnék után tagcsere következett, Soós Gábor ült a dobok mögé. Nem sokkal később teljesen szétesett ez a felállás, és csupán Bóta Balázs és Jutasi Sándor maradtak együtt.
1995 első napján újralakult az együttes. A két új tag Landy László dobos és Viszt Viktor énekes lett. A nyáron a Teve Sound stúdióban felvették a második demót (Reality/Evolution) Váradi Péter billentyűs vendégszerepelésével. Viszt hamar odébb állt, ezután az énekes posztját Illésfalvy Iván töltötte be, akivel decemberben rögzítették az Afterwards kislemezt. A kritikusok egyre többet foglalkoztak az együttessel. 1996 júliusában részt vettek az LMS-fesztiválon, majd felvették a Rambling 1 című kislemezt. Szeptemberben a pécsi Progresszív Fesztivál vendégei voltak. Erre az eseményre Tóth István ideiglenes visszatért az együttesbe, majd később véglegesen is. Még az év vége előtt elkészült Rambling 2.
1997-ben a Psychotic Waltz előzenekara voltak az amerikai prog-metal együttes magyarországi fellépésén. Novemberben másodszor is felléptek a Progresszív Fesztiválon, majd az év végén még egy tagcsere következett: Felföldi Péter lett az új énekes. 1998-ban vették fel a háromszámos Angels című demót, melyen vendégzenészként szerepelt Hohl Árpád. Az együttes nemsokára újabb tagcseréken esett át.1999 legelejétől Bátky Zoltán (alias BZ) vette át az énekesi posztot. A régi dalokat átdolgozták és folyamatosan születtek az új témáik is, mint a zenekar legelső klipjét adó "Between Two Worlds", a keleties "Full Moon" vagy az indián mitológiából merítő "Wendigo". Az említett videoklipet 2000-ben forgatták. Ekkor már Baki Ádám személyében "élő" billentyűssel gazdagodott az együttes, és Somogyi Zoltán basszusgitározott a zenekarban, de hamarosan Temesi Bertalan vette át a hangszert. A zenekar 2000 végén kezdte meg első albumának felvételeit és jó egy évig dolgoztak a HSB Stúdióban Hidasi Barnabás hangmérnökkel.
Az Angelo Salutante című album 2001 áprilisában jelent meg a Nail Records gondozásában. A fogadtatás minden előzetes várakozást felülmúlt. Az albumot később licencelte a spanyol Heavencross Records, de bővített formában kiadták Koreában, Tajvanon és Japánban is. A lemezt természetesen koncertturné is követte, melynek jó részében a szentgotthárdi Da Capo volt a Stonehenge vendége. Kiemelkedő állomás volt a 2001-es Summer Rocks fesztivál, melyen egyetlen hazai zenekarként vett részt a csapat.
2002-ben felléptek a Sziget Fesztiválon, a következő évben pedig első és egyedüli magyar fellépőként a Stonehenge főműsoridőben játszott a hollandiai ProgPower Europe fesztiválon. Bár akkor még nem tudták, de ez a fellépés volt eddigi utolsó élő koncertjük.2003-ban több részletben felvételre került egy Shaman munkacímű EP, amely azonban sosem látott napvilágot. Három dalának feléneklése után BZ először a tagok aktivitásának, motivációjának visszatérését kérte a többiektől, de egy hónapos türelmi idő elteltével az év nyarán távozott. Ezt követően a Stonehenge gyakorlatilag leállt, és a tagok visszavonultak.
A Stonehenge 2005-ben még megpróbálkozott egy kissé furcsa lépéssel: bekerült az együttesbe Kyrah énekesnő (ex-Without Face és férfi énekesként az Angliából érkezett, japán származású Fumio Takaki. A 2005-ben kiadott Nerine azonban nem volt más, mint a 2003-ban még BZ-vel készült kiadatlan EP újraénekelt, újrakevert változata, új dalszövegekkel és dallamokkal, kiegészítve egy pár perces instrumentális szerzeménnyel.
Az EP kiváló kritikákkal és meglepően magas eladási statisztikákkal büszkélkedhetett. A Mahasz nemzetközi kislemez lista 2. helyét érték el, egyedülálló módon a hazai progmetal színtér képviselői közt. Ez a legutolsó felállás már egyáltalán nem koncertezett, további érdemi munka nem folyt az EP megjelenését követően, így a Stonehenge 2005 második fele óta - bár hivatalosan nem szűnt meg - de inaktív.
A 2009 óta újra együtt dolgozó, ám élőben az idei MetalFest nagyszínpadán visszatérő Stonehenge tagjai már nagyon várják a csillebérci fellépést. A koncert gerincét természetesen az idén tíz éves album, az Angelo Salutante dalai adják, ám semmiképpen nem szabad azt hinni, hogy langyos "nosztalgiabuli" várható. A zenekar ugyanis folyamatosan dolgozik új dalokon, amelyek közül pár már a MetalFesten is elhangzik.
A lemezes felállásból Bóta Balázs gitáros, Bátky 'BZ' Zoltán énekes és Szabó Kristóf dobos mellett a zenekar alapító basszusgitárosa, Jutasi Sándor, valamint az After All-ból és a Haelo-ból ismert Czapár János billentyűs alkotja a Stonehenge-et, amely a MetalFest-fellépést követően 2011 ősszén egy nagyszabású koncertet is tervez, melyen megünneplik a tíz éves Angelo Salutante albumot, valamint még több újdonsággal jelentkeznek.
