Gli Allhelluja sono un gruppo italiano autore di un mix molto "sporco" tra stoner rock, hard rock e metal sulla scia degli Entombed.
Il progetto nasce nel 2003 su idea di Stefano Longhi (batteria) e Massimo Gajer (chitarra), al microfono viene invitato il cantante di Hatesphere e chitarrista dei Barcode Jacob Bredahl, la line-up viene completata dal bassista Roberto Gelli.
Nel maggio 2005 viene pubblicato il primo LP della band, dal titolo Inferno Museum di 10 tracce, attraverso la Scarlet Records, di cui lo stesso Stefano Longhi è uno dei proprietari. Precedentemente grazie ai primi demo il gruppo era stato contattato anche dalla Roadrunner Records. L'album riceve recensioni entusiaste da tutti le principali riviste del settore e la band viene paragonata a gruppi del calibro di Entombed, Down, Unsane, Raging Speedhorn, Gluecifer e addirittura Black Sabbath.
Nel settembre 2006 è stato pubblicato il secondo album dal titolo Pain is the Game, registrato negli studi Smart 'n Hard di proprietà di Jacob Bredahl e prodotto da Tue Madsen (Heaven Shall Burn, Mnemic, The Haunted, Sick of it All). I responsi sono stati anche migliori del primo LP grazie a una maggiore varietà delle canzoni e ad un sensibile miglioramento delle capacità vocali del cantante danese.
È stato annunciato che uscirà al pubblico nel periodo di Giugno-Luglio 2007 un cofanetto speciale a tiratura limitata intitolato Into The Inferno - Into The Pain contenente i due album della band e dei gadget a sorpresa. Tale collezione è stata messa in vendita a inizio Giugno in esclusiva ai Gods Of Metal 2007.
Secondo le parole di Stefano Longhi in una recente rivista sul mensile di settore Metal Hammer Italia, il nuovo album della band è previsto per l'estate del 2008.