У серпні того ж року на фестивалі в Вакене барабанщик познайомився з Атерових (Співав Матісен), очолював у той час любительську групу. Тьодалв сказав йому, що шукає музикантів для нового проекту, і дав послухати компакт-диск з пробними записами. Атерових дуже сподобалося брутальне звучання платівки, і він прокручував диск знову і знову. Зрештою, він знову зателефонував Тьодалвом і запропонував свої послуги як вокаліста.
Тепер групі не вистачало тільки басиста і другого гітариста. Обидві вакансії були закриті за допомогою того ж Атерових, який привів музикантів зі своєї банди, Мемнока (Хекон Дідріксен) і Елворна (Крістіан Хаген). У вересні 1999-го повноцінна команда приступила до репетицій, а до грудня вже підготувала п'ять композицій, об'єднаних під назвою "Illusions Of Evil".
Як водиться, демку розіслали по різних лейблів, але відповідна реакція перевершила всі очікування. Колективу надійшло близько десяти пропозицій від великих компаній запису, з яких музиканти зупинили свій вибір на "Nuclear Blast". На початку 2000 року "Susperia" уклали четирехальбомний контракт з цією фірмою, а восени колектив вирушив у знамениту шведську студію "Abyss", де під керівництвом Петера Тагтгрен справив на світло свій перший полнометражнік, "Predominance". Обраний групою стиль можна було описати як брутальний метал з мелодійними вкрапленнями. Якщо на "Illusions Of Evil" команда ще використовувала клавішні, то на "Predominance" суворі норвежці відмовилися від них, щоб надати своїм звучанням більшої агресивності.
Дебютний концерт "Susperia" відіграли в столичному місті Осло, а на розігріві у них виступали "Ragnarok" і "Alsvartr". У 2001 році відбулися повноцінні європейські гастролі, протягом яких команда ділила майданчика з "Dimmu Borgir", "In Flames", "Nevermore", "Lacuna Coil" і "Destruction". Тим часом наклад "Predominance" перевалив за 10000 копій, група підписала контракт на дистрибуцію з корейською фірмою "Pony Canyon", а журнал "Terrorizer" надрукував двохсторінковий статтю про "Susperia".
До кінця року колектив повернувся до студії "Abyss", де були записані всі інструментальні партії для другого альбому (вокал записувався в "BBM Studio"). Реліз "Vindication" відбувся в травні 2002-го, після чого команда активно гастролювала по Європі в компанії з "Borknagar", "Suidakra", "Windir", "Fintroll" і "Mortiis". Свій третій альбом норвезькі брутальщікі записували в двох студіях, "Subsonic Society" (Осло) і "Studio Fredman" (Гетенбург), а вийшов він у травні 2004-го. "Unlimited" на той момент став найбільш комерційно успішним опусом "Susperia". Диск дебютував в норвезьких чартах під номером 43 і зібрав купу захоплених відгуків не тільки в Європі, але і за океаном. На підтримку альбому пройшов 9-тижневий Євротур, а роком пізніше норвежці гастролювали в одній зв'язці з "Testament".
Щоб скрасити очікування чергового лонгплея, восени 2005-го команда випустила EP "Devil May Care", куди крім оригінального матеріалу були включені і кавери. На подив самих музикантів платівка потрапила в національний Топ 20, чого раніше з норвезькими метал-бандами не траплялося. Втім, через півтора року їм вдалося повторити цей успіх і альбом "Cut From Stone" дебютував в "Norways National Artist Charts" під номером 18.