Po zrealizowaniu „As Live…”, Singer oraz Naylor opuścili grupę, a w ich miejsce zespół zasilili: Phil Greenhouse (perkusja, zastąpiony wkrótce przez Jasona Bowlda) i Wayne Banks (bas). W tym składzie grupa nagrała album „Blood & Belief”, który ukazał się w roku 2004. Kolejne lata upłynęły pod znakiem licznych rotacji w składzie oraz koncertów. Ostatecznie Blaze zdecydował się również na modyfikację nazwy zespołu, która w 2007 roku przyjęła formę: Blaze Bayley. Drugi album koncertowy w dyskografii grupy ukazał się w sierpniu tego samego roku; „Alive In Poland” został zarejestrowany w Katowicach podczas festiwalu Metalmania 2007. Na rynku ukazała się również płyta DVD z zapisem tego występu.
Bardzo dobrze przyjęty krążek „The Man Who Would Not Die” został wydany w lipcu 2008 roku. Zespół zarejestrował ten materiał w składzie: Blaze Bayley (śpiew), Nick Bermudez (gitara), Jay Walsh (gitara), David Bermudez (bas) oraz Lawrence Paterson (perkusja). Dwa lata później w ręce fanów trafił jego następca "Promise and Terror" (2010) - piąty album w solowym dorobku artysty.