Дотримуючись модних віянь Роб завів дружбу з Трент Резнор з "Nine inch nails", і під його впливом заснував індастріал-команду "Two". Однак цей проект виявився провальним, і Халфорд вирішив повернутися до своїх металевим коріння, зайнявшись підготовкою нового матеріалу.
У його нову групу, яку він охрестив своїм ім'ям, також увійшли ветеран "Riot" і "Spastic ink" барабанщик Роб Ярзомбек, гітаристи Патрік Лачмана (екс-"State of the art", "Diesel machine") і Майк Класяк, а також колега Роба по "Two" басист Рей Ринд.
На своєму сайті Халфорд виклав трек "Silent Screams", який вразив фірму "Sanctuary", що запропонувала укласти з нею контракт. У результаті нового співробітництва на світ з'явився альбом "Resurrection", дуже захоплено прийнятий слухачами та музичної пресою. Наприклад, журнал "Classic Rock" назвав цю платівку кращим творінням Роба за всю його кар'єру, включаючи час перебування в "Judas priest". І дійсно альбом становив потужний класичний хеві, трохи осучаснений. Після виходу диска "Halford" півроку провели на гастролях, об'їздивши Північну і Південну Америку, Європу і Японію.
Під час цього туру група взяла участь на фестивалі "Rock In Rio", де виступила перед двохсоттисячного аудиторією. На основі цього концерту у 2001 році вийшов подвійний "живий" альбом "Live Insurrection". Туди увійшли пісні з репертуару "Halford", "Fight" та "Judas priest", а на треку "The One You Love To Hate" гостював Брюс Дікінсон з "Iron maiden".
У тому ж році музиканти "Halford" розважалися сторонніми справами: Майк випустив свій третій сольник, "The Spilling", Ярзомбек і Ринд попрацювали в "Spastic ink", а Лачмана замутив новий проект з лідером "Prong" Томмі Віктором і барабанщиком Деном Лауда. Тим не менш, до середини 2002-го у халфордовцев був готовий другий студійний альбом, "Crucible". Цей реліз нічим не поступався своєму попереднику, і лише додав групі успіху. Слідом за виходом диска пішла серія виступів команди на різних європейських фестивалях типу "Gods Of Metal", "Sweden Rock Festival", "Rockwave", "With Full Force" та інших. На цих концертах Халфорд і компанія пригощали публіку не тільки своїми речами, а й класикою з репертуару "Judas priest".
Слідом за Європою "Halford" відвідали Північну Америку. Щоправда, в цій затії не брав участь Лачмана, оскільки був зайнятий в "Diesel machine". Його обов'язки довелося виконувати продюсеру гурту Рою Зеду. Він же займав місце гітариста і на японських гастролях, які команда провела в компанії з фінами "Children of Bodom".