Niepowodzenie **Fight** i kompletna klapa projektu **2wo** spowodowała, że Rob Halford znalazł się na rozdrożu. Z **Judas Priest** odchodził będąc na szczycie, tymczasem ledwie kilka lat później wydawał się być muzykiem zapomnianym, zagubionym i sfrustrowanym. Na szczęście, w końcu zdecydował się na powrót do tego, co wychodziło mu najlepiej - do klasycznego heavy-metalu. W 1999 zebrał młodych muzyków, wśród których znaleźli się gitarzyści Mike Chlasciak i Patrick Lachman, basista Ray Riendenau oraz perkusista Bobby Jarzombek i rozpoczął z nimi pracę nad debiutanckim albumem grupy, która została ochrzczona nazwą **Halford**. Początkowo pracowali z producentem Bobem Marlette, który zagrał na gitarze na płycie **2wo**, ostatecznie jednak producentem i współkompozytorem został Roy Z znany ze współpracy z **Brucem Dickinsonem**. Zespół trafił też pod skrzydła Roda Smallwooda - menedżera **Iron Maiden**. Efekt pracy okazał się znakomity - płyta **Resurrection** została znakomicie przyjęta. Wielu krytyków uznało ją za najlepszą płytę heavymetalową od wielu lat. Na albumie znalazło się dwanaście klasycznych heavymetalowych utworów, wśród których znalazł się między innymi //The One You Love To Hate// - duet Halforda z Brucem Dickinsonem z **Iron Maiden**. Sukces płyty potwierdziła niezwykle udana trasa koncertowa trwająca całą drugą połowę 2000 roku (zespół występował między innymi w charakterze supportu dla **Iron Maiden** w Anglii, zagrał także na Rock In Rio). Zarejestrowane podczas niej występy posłużyły za kanwę koncertowego albumu **Live Insurrection**, który potwierdził znakomitą dyspozycję Halforda i klasę muzyków z nim współpracujących. Rok 2002 to premiera kolejnego krążka studyjnego - **Crucible**, który okazał się równie udany jak debiut, choć był dziełem zdecydowanie cięższym brzmieniowo i agresywniejszym muzycznie. Trasa koncertowa nie obyła się bez problemów, wiele koncertów zostało odwołanych ze względu na wyczerpanie lidera. Po raz kolejny sporo występów zostało nagranych. Światło dzienne ujrzały one jednak dopiero siedem lat później w roku 2010, kiedy to premierę miało DVD i CD **Live in Aneheim**, zawierające także kilka numerów nagranych w Tokio w czasie japońskiej części trasy. W trakcie trasy koncertowej Patrick Lachman zdecydował się odejść i dołączyć do grupy **Damageplan**, obyło się jednak bez szukania następcy, bowiem do zespołu dołączył po prostu producent Roy Z. W 2003 miała miejsce jeszcze jedna roszada w składzie - ze względu na rodzinną tragedię zespół opuścił Ray Riendenau, a na jego miejsce trafił Mike Davis z **Lizzy Borden**. Po zakończeniu trasy koncertowej, w lipcu 2003 wraz z ogłoszeniem powrotu lidera do **Judas Priest** zespół znacznie ogranicza działalność, okazjonalnie koncertując.