Вже після декількох концертів Бред кудись зник, і крім гітарних справ Метт приватизував і вокальні функції. Наступні два роки команда відточувала свій саунд, паралельно вирішуючи нескінченні кадрові проблеми. Незважаючи на те, що на конкурсі в Орландо Хіфі виграв звання "Best Metal Guitarist", без другого гітариста було важко обходитися, і нарешті підходяща кандидатура була знайдена в особі Корі Бьюлі.
Цей хлопець був упертим фанатом дез-металу, і з його появою звучання "Trivium" придбало відповідний присмак. Ще до приходу Корі в 2003 році група записала демо-EP, за допомогою якого їй вдалося отримати контракт від невеликого німецького лейблу "Lifeforce Records".
Навесні 2003-го фірма випустила альбом "Ember to Inferno". Одна з пісень з цього диску була включена в бонусний CD якогось металевого журналу, і саме на ньому її почув Монте Коннер. Цей тип з вищого керівництва "Roadrunner Records" вже працював з "Slipknot" і "Sepultura" і тому відразу помітив незвичайний потенціал "Trivium". Тим часом продажі "Ember to Inferno" йшли добре, і лейбл поспішив укласти з музикантами угоду, виділивши їм на допомогу продюсера Джейсона Сьюкофа. Влітку 2004-го почалися сесії другого альбому, а восени того ж року команда провела кілька турів в компанії з "Machine Head", "Iced Earth", "Killswitch Engage" і "Fear Factory".
До того моменту колектив нарешті знайшов постійного бас-гітариста, яким став Паоло Греголетто. Популярність "Trivium" росла з кожним концертом, а подальшому просуванню справ допоміг грамотний промоушн. На підтримку "Ascendancy" фірма випустила чотири сингли, причому на кожен з них був знятий відеокліп.
В результаті альбом потрапив до заповітного біллбордовскіх Топ 200 (151-е місце) і опинився на четвертій позиції в розділі "Heatseekers". Як не дивно, але по той бік океану успіх команди був ще більше: в Британії "Ascendancy" швидко став золотим і дістався до 78-го рядка тамтешніх чартів. У 2005 році група стала учасником таких солідних фестивалів як "Download" і "Ozzfest", а, крім того, багато гастролювала по Північній Америці, Англії і Японії, ділячи майданчика з "Arch Enemy", "Children Of Bodom", "Amon Amarth "," Danzig "і т.п. У 2006-му журнал "Kerrang!" організував випуск триб'юту, присвяченому 20-річчю "Master Of Puppets", і "Trivium" виявилися задіяними в цьому проекті.
Саме тут Хіфі вперше змінив свій вокальний стиль, що згодом відбилося на третьому альбомі групи. І дійсно, якщо перші релізи характеризувалися слівцем "металкор", то на "The Crusade" колектив заграв в дусі ранньої "Metallica". У зв'язку з цим думки фанів розділилися, однак цей факт не завадив новій роботі "Trivium" зламати Топ 40 багатьох країн світу.