Gli Annihilator devono i loro natali alla città di Ottawa grazie all'incontro tra il chitarrista Jeff Waters e il cantante John Bates, che avviene nel lontano 1984. Waters viene iniziato all'ascolto del thrash metal, e con Bates, dopo aver allargato i propri orizzonti musicali, fino a quel momento limitati all'heavy metal, registra la canzone Annihilator (non quella di King of the Kill). Non tarda ad unirsi a loro il bassista Dave Scott, con il quale ha inizio la promozione del loro demo. Paul Malek in seguito completa la formazione, portando sicurezze anche alla batteria, mentre i chitarristi Myles Rourke e Joe Bongiorno continuano a fungere da session member.
Segue la registrazione del demo chiamato Welcome to Your Death prodotto da Rob Lange. In seguito alla dipartita di Malek, la line-up conosce un periodo di profonda instabilità. Nell'anno 1986 Waters registra con Malek Phantasmagoria. Dopo un ulteriore demo, la band comincia ad ottenere svariate offerte da svariate case discografiche, ed in seguito allìingaggio di un manager e all'incontro con Ray Hartmann iniziano i lavori per il primo album. Questa è la storia del debut album Alice in Hell.
Waters ingaggia il bassista e cantante Randy Rampage, il bassista Wayne Darley, il chitarrista Dave Scott Davis. A lanciare sul mercato Alice in Hell è la Roadrunner Records, e al dimissionario Dave Scott Davis subentra Anthony Greenham. Anche Randy Rampage lascia la band, ma questo non impedisce agli Annihilator di intraprendere un tour in terra Canadese insieme ai Testament. La Roadrunner consiglia l'ingaggio di Coburn Pharr Omen, e nell'anno 1990 la band pubblica il secondo album intitolato Never, Neverland. Gli Annihilator organizzano quindi un tour europeo per promuovere l'album, facendo anche da spalla ai Judas Priest, alle prese con la promozione di Painkiller. Pharr lascia il gruppo, al suo posto arriva Neil Goldberg. Poco dopo anche Ray Hartmann rassegna le dimissioni e viene sostituito da Mike Mangini. A questo punto Waters, Randall, Goldberg e Mangini si mettono a lavoro per quello che sarebbe poi diventato Set The World On Fire, intraprendendo un tour in tutta Europa. Mangini, infortunato, viene sostituito da Randy Black. Alla fine del tour gli Annihilator escono con la raccolta Bag of Tricks, contenente i loro maggiori successi. Nell'anno 1994 Randall lascia la band durante la registrazione di King of the Kill, unici rappresentanti degli Annihilator sono Randy Black e Jeff Waters. Per promuovere l'album, viene fatto un tour europeo ed uno giapponese. Nell'anno 1996 Waters, Black e Davis decidono di pubblicare Refresh the Demon. Che segna l'inizio di un inesorabile declino. Il tour promozionale per il nuovo lavoro non riscuote consensi eclatanti, ed è costellato da sostituzioni e defezioni continue, ivi compresa quella della Roadrunner, a cui subentra la CMC International. Nell'anno 1997 gli Annihilator pubblicano Remains, interamente registrato da Waters, a cui non segue nessun tour. Nel 1999 Randy Rampage, Ray Hartman e Jeff Waters iniziano a lavorare per quello che poi si sarebbe chiamato Criteria for a Black Widow, firmato Roadrunner Records. A Wayne Darley subentra Russell Bergquist, e una volta consolidata la line-up, iniziano due tour per l'Europa. Rampage lascia di nuovo la band e Waters nell'ultimo spettacolo del tour veste i panni anche del cantante. Alla voce viene poi ingaggiato Joe Comeau. Carnival Diablos è il nome della successiva opera degli Annihilator. Nel 2002 Hartmann lascia. Esce Waking the Furye viene fatto un tour in tutta Europa ed in Giappone. Durante questo tour, la band registra il live Double Live Annihilation. Nel 2003 a Comeau subentra Dave Padden, che con Waters e Mangini registra il decimo album, All for You. Ha inizio una fase di ulteriore declino. I due tour europei e il supporto ai Judas Priest li riportano a galla, e si uniscono al gruppo Sandor Bret e Rob Falzano. Nel 2005 esce l'undicesimo disco, chiamato Schizo Deluxe. Nel 2007 è stato dato alle stampe Metal, pieno di collaborazioni e comparse importanti, che non riscuote un gran successo e porta ad un tour di spalla ai Trivium. Nell'ottobre dell'anno 2009 tramite la SPV Records viene pubblicato il DVD Live at Masters of Rock, e gli Annihilator firmano un contratto discografico con la Earache Records. Viene ingaggiato
il bassista Alberto Campuzano per il tour mondiale schedulato. Il 17 maggio 2010 vede la pubblicazione del loro tredicesimo album, Annihilator. L'album raccoglie consensi in quantità grazie alle sonorità thrash metal ed alla presenza di assoli di chitarra in quantità. Poco dopo la band intraprende un tour europeo, che vede impegnato alla batteria come session member Carlos Cantatore, musicista Italiano, che Jeff Waters ha conosciuto e voluto con sè per quest'ennesima fatica.