Paradox
Завдяки цьому вже восени музиканти поставили свої підписи на контракті з "Roadrunner Records", притулок таких монстрів як "Metallica", "Slayer" і "Mercyful Fate". У лютому 1987-го вийшло друге демо, "Mystery".
"Rock Hard" тут же знову відреагував, визнавши "Mystery" Демко року, а "Paradox" - кращою новою командою. Крім того, реліз отримав схвальні відгуки по всьому світу, а особливо - в Японії. Також колектив взяв участь у записі збірки "Teutonic Invasion", подарувавши для цієї платівки трек "Pray To The Godz Of Wrath". У травні 1987-го з продюсером Калле Трапп ("Saxon") був записаний диск "Product Of Imagination", вихід якого викликав цілу бурю захоплення.
На думку журналу "Rock Hard" "Paradox" зі своїм дебютним альбомом обставили Оззі Осборна і "Judas Priest", а "Metal Hammer" назвав платівку кращим німецьким дебютом з часів "Helloween", "Product Of Imagination" отримав п'ять зірок у "Musikexpress "і навіть англійська" Kerrang! " присвоїв групі звання "німецької Metallica". Крім цього читачі "Rock Hard" і "Metal Hammer" визнали "Paradox" кращою німецькою бандою після "Scorpions" і "Accept" і кращими новачками 1988 року. Колектив порадував своїх фанів і концертами, відправившись у турне зі швейцарцями "Drifter". За цим послідували дати з "Overkill", "Helloween", "Exodus", "Candlemass" і поява групи на солідних європейських фестивалях, голландському "Dynamo Open Air" та португальською "Festa Avante".
Але не все складалося вдало - починаючи з кінця 1988 року склад почало лихоманити. Першим пішов Роланд Став, і разом з тим команда залишилася без менеджменту. Басуху вручили Маттіасу Шмідту, але тут прийшла черга гітариста, і Маркуса Спиця змінив Дітер Рот. У даній конфігурації з продюсером Харрісом Джонсом ("Helloween", "Voivod") "Paradox" записали "Heresy". Альбом хоч і отримав позитивні відгуки, але не здобув такого успіху як його попередник.
В кінці 1989-го в групі знову змінився гітарист. Але колишньому учасникові "Cronos Titan" Каю Пейсману не вдалося довго пограти у складі, оскільки невдовзі контракт з "Roadrunner" був розірваний, і проект впав у кому. Минуло майже десять років, перед тим як преса і рекорд-лейбли почали виявляти інтерес до творчості команди. На цій хвилі Стейнхауер почав готувати новий матеріал, запросивши на допомогу Пейсмана. Через деякий час з приходом братів Алекса (ударні) та Олівера (бас) Хольцвартов новий склад був остаточно сформований. Офіційний камбек "Paradox" відбувся в серпні 1999-го на фестивалі "Wacken Open Air". На наступний рік на лейблі "GSM Records" вийшов третій альбом групи, "Collision Course".
На жаль, після цього Стейнхауер змушений був відійти від справ, оскільки йому довелося поховати кількох родичів. Лише в 2005 році Чарлі оговтався від бід і разом з Пейсманом почав набирати новий склад. Ряд кадрових перестановок закінчився придбанням ритм-секції в особі Роланда Яходи (ударні) і Оллі Келлера (бас). У 2006-му відновилися "парадоксальні" концерти, а на початку 2008-го вийшов альбом "Electrify".