W 1994 roku zespół podpisał kontrakt z wytwórnią Roadrunner Records i wydał swój debiutancki album „Burn My Eyes”, który okazał się całkiem sporym skcesem, rozchodząc się w nakładzie ponad 500 000 egzemplarzy. Płyta stała się znakiem rozpoznawczym grupy i była jednym z najlepiej przyjętych debiutów w historii. Dzięki temu grupa wyruszyła w bardzo długą trasę koncertową z zespołem Slayer. 12 grudnia 1994 roku zawitali na jeden koncert do Zabrza. Ich wspólna trasa przyniosła grupie ogromny wzrost popularności na świecie.
Niestety w zespole przyszedł czas na zmiany. Znów odszedł perkusista – miejsce Knotos’a zajął Dave McClain, który pozostał w nim do dziś. Zespół zaczął pracę nad nowym materiałem, który ukazał się na płycie „The More Things Change…”w 1997 roku. Choć wydawnictwo znów odniosło sukces i potwierdziło klasę formacji, nie zastopowało to zmian w grupie. W niezbyt miłych okolicznościach z formacją rozstał się Logan Mader – jego miejsce zajął Ahure Luster.
Na kolejną płytę fani musieli czekać dwa lata. W 1999 roku zespół zatrudnił do współpracy Rossa Robinsona – producenta znanego ze współpracy z takimi gwiazdami jak KoRn, Slipknot, Soulfly czy Sepultura. Ze względu na włączenie do swojego stylu muzycznego elementów hip-hopowych, wielu wiernych fanów odwróciło się od zespołu.
Kolejny album to również komercyjna klęska – jednak tutaj upatrywano jej przyczyny w dacie premiery, która miał miejsce 2 października 2001 roku – jak się okazało tuż po tragicznych wydarzeniach z 11 września. Promocję albumu „Supercharger” miała wspierać trasa koncertowa, podczas której zespół ponownie zawitał do Polski – tym razem na dwa koncerty. Grupa zagrała w Warszawie i Krakowie, a supportem była polska grupa None.
W 2002 roku nastąpiła kolejna zmiana w składzie grupy – miejsce Lustera zajął Phill Demmel (kolega Roberta Flynna z czasów Vio-lence). Luster odszedł z zespołu w wyniku rozbieżności zdań między nim a Flynnem.
Następnym wydawnictwem okazała się koncertowa płyta „Hellalive” z 2003 roku. Pomimo tego, iż z zespołem rozwiązała kontrakt wytwórnia Roadrunner Records, grupa pozostała w jej europejskiej filli. Pozwoliło to im na wydanie kolejnej studyjnej płyty pod tytułem „Through the Ashes of Empire” (płyta jednak nie ukazała się w USA). Zespół zaczął odzyskiwać lekko nadwątloną popularność – płyta zbierała jedynie pochlebne recenzje. Dzięki temu zespół w 2004 roku ponownie podpisał kontrakt z Roadrunner Records. Płyta, wzbogacona o jeden dodatkowy utwór została wypuszczona na rynek amerykański, gdzie również została dobrze przyjęta przez fanów. W ramach trasy promocyjnej zespół przyjechał do Polski, aby zagrać koncert w Warszawie.
W 2005 roku zespół wydał swoje pierwsze dvd. Nosiło ono tytuł „Elegies” i było zapisem koncertu jaki miał miejsce w Brixton Academy w Londynie.
2007 rok do premiera kolejnej płyty. Album „The Blackening” w ciągu dwóch tygodni osiągnął lepsze wyniki sprzedaży niż poprzedni w ciągu trzech lat. Już samo to może świadczyć o komercyjnym sukcesie płyty. W czerwcu tego roku otrzymali nagrodę Metal Hammer w kategorii Best Album, a Flynn dodatkowo odebrał tytuł Golden God. Dodatkowo Kerrang uhonorował formację za Album of the Year. Miesiąc później na stadionie Wembley supportowali Metallikę.
Na początku następnego roku pojechali w trasę koncertową po Ameryce Północnej. W marcu odwiedzili między innymi Zjednoczone Emiraty Arabskie oraz Izrael. W październiku pojawili się razem ze Slipknotem w Australii. Pod koniec roku – Slipknot, Children of Bodom oraz Machine Head – zagrały na europejskim tournee. Formacja nagrała cover z repertuaru Iron Maiden – „Hallowed Be Thy Name”, która razem z między innymi Dream Theater oraz Trivium znalazła się na składance w hołdzie klasykom heavy metalu – „Maiden Heaven: A Tribute to Iron Maiden”. W 2008 roku zespół znów odwiedził Polskę i zagrał jak na razie swój ostatni koncert w naszym kraju jako support przed zespołem Metallica.
W czerwcu 2009 roku pojawili się razem z Megadeth oraz Slayerem na serii koncertów w Kanadzie.