В мае 2001 года, после репетиций в новом составе с вокалистом Rob Thompson, группа уже в студии, записывает демо версии нескольких треков с нового альбома, в том числе одну песню, посвященную участнику легендарных Thin Lizzy Philip Lynott... Речь идёт о Ballad of a Thin Man, которая была прослушана даже матерью Лайнота, Ms. Philomena Lynott, и она сказала: "Фантастика! Филу бы это понравилось!" Все записанные композиции вошли в альбом THE HEADLESS HORSEMAN.... Оформление его сделал знаменитый австралийский художник в стиле "фэнтези" Russell Bennett... Полноценная сессия записи альбома была отложена на несколько месяцев, поскольку барабанщику группы было произведено оперативное вмешательство по поводу ущемления паховой грыжи. Однако осенью 2001 года за 4 недели дело было сделано. The Headless Horseman был записан и ещё три недели производилось микширование и мастеринг. Группа продемонстрировала невиданный прогресс во всех отношениях, начиная от качества самих композиций, и заканчивая безупречно отшлифованным звуком! Диск звучит так тяжело и агрессивно, как не звучат даже последние работы самих Iron Maiden, Judas Priest и Manowar, вдохновивших когда-то австралийцев на творчество! Также была записана специальная версия композиции 'The Patriot' -посвященной храбрым воинам из USA, Australia, UK, Germany, Italy и Russia ведущим борьбу с терроризмом. 11 марта 2002 года альбом Headless Horseman увидел свет!