A korábban is együtt zenélő Mark Tremonti (gitár), Brian Marshall (basszusgitár) és Scot Phillips (dobok) zeneileg is továbblépve korábbi zenekarukon egy markáns, friss orgánumot kerestek a jövőbeni közös zenéléshez, és azt a két lemezt kiadó The Mayfield Four énekesében, Myles Kennedyben találták meg. A zenekar azonnal hozzálátott azoknak a daloknak a kidolgozásához és rögzítéséhez, melyek nagy részét maga a gitáros, Mark Tremonti írta. Az eredetileg Tremonti által egy kézi felvevővel rögzített első számokból már 2004 augusztusában megjelent első albumuk One Day Remains címmel. A banda mind az Egyesült Államokban, mind Európában megturnéztatta bemutatkozó anyagát, sőt komoly sikernek könyvelték el, hogy a kanadai pankráció-sztár, a WWE világbajnok Edge, a lemezről a Metalingus című számot választotta bevonulási zenéjének.