Вслед за этим выступлением последовала серия концертов команды на различных европейских фестивалях как Gods Of Metal, Rockwave, With Full Force и других. На них Хэлфорд и его группа исполняли не только свои композиции, но и классику из репертуара Judas Priest.

Вслед за Европой Halford посетили Северную Америку. Правда, в этом турне не принимал участие Лачман, поскольку был занят работой в Diesel Machine. Его обязанности пришлось выполнять продюсеру группы Рою Зеду. Он же занимал место гитариста и на японских гастролях, которые команда провела в компании с дэт-металистами Children of Bodom.

В апреле 2003 года из-за обострившихся личных проблем группу покинул Рэй Риндо, на место которого был приглашён Майк Дэвис из Lizzy Borden.

В скором времени группа Хэлфорда и их менеджер Джон Бэкстер покинули Sanctuary Records за два альбома до истечения контракта. Поводом стала обида на Рода Смоллвуда и его людей за недопродвижение последнего альбома Crucible с конечной целью вернуть Роба в Priest. Планируемый новый альбом Хэлфорд собирался профинансировать сам, однако планам не суждено было сбыться: вопреки многочисленным заявлениям о невозможности воссоединения с Judas Priest 11 июля 2003 года состоялось событие, которое поразило весь музыкальный мир: после 12 лет сольной карьеры Роб Хэлфорд объявил о своём возвращении в Judas Priest.

Выступления с Black Sabbath и Trinity

В самом начале своей сольной карьеры Хэлфорд на два выступления стал вокалистом Black Sabbath, поскольку заменял Ронни Джеймса Дио в ноябре 1992 года. Сам Ронни принял решение покинуть группу, когда Оззи Осборн в очередной раз заявил об уходе со сцены и пригласил Black Sabbath открывать два его прощальных концерта, которые таковыми не оказались. Дио счел это унижением, но он умудрился сохранить лицо благодаря удачному стечению обстоятельств: его контракт истекал 13 ноября 1992 года, а концерты Оззи были запланированы на 15-е и 16-е. Роб Хэлфорд, который являлся давним другом Дио и земляком Sabbath, пришёл на помощь коллегам.

25 августа 2004 года (на свой 53-й день рождения) он опять был приглашён на место вокалиста группы для концерта на Оззфесте поскольку Оззи Осборн не мог выступать из-за бронхита.

Ещё одно знаменательное сотрудничество произошло во время проведения мирового турне The Brave New World tour Iron Maiden, в котором британских металлистов сопровождали Halford и Queensrÿche: во время выступления Halford Роб Хэлфорд, Брюс Дикинсон (вокалист Iron Maiden)и Джефф Тэйт (вокалист Queensrÿche) выходили на сцену вместе для исполнения песни «The One You Love To Hate» (с альбома Роба Resurrection 2000 года). Этот альянс породил массу слухов о грядущем совместном альбоме трех вокалистов под названием The Three Temors (или Trinity), примерной датой релиза называлось лето 2001 года. Продюсерами альбома должны были выступить Рой Зи и Род Смоллвуд. Грядущий релиз должен был содержать по одной песне из творчества Iron Maiden, Judas Priest, Queensrÿche, сольных работ Дикинсона и Хэлфорда, а также несколько кавер-версий. Уже в конце 2000 года представители Sanctuary Records опровергли возможность записи диска, тогда как Роб Хэлфорд в то же время обещал его появление в конце 2001 года. Финальный аккорд поставил Дикинсон, который в октябре 2001 года заявил, что музыканты заняты своей основной работой и им не хотелось бы подставлять Sanctuary Records, выпуская достаточно сырой материал. С того времени музыканты хранят по этому поводу молчание, а фирма Sanctuary Records отрицает наличие каких-либо письменных договоренностей между артистами.