Після довгих пошуків гідного вокаліста вони зупинили свій вибір на Йорн Ланде, який співав тоді в "The Snakes". Присутні з комерційних хард-рокових команд, хлопці вирішили створити щось відмінне від того, чим вони займалися раніше. У 1999 році, виданий спочатку лише в азіатському регіоні (в Європі та Америці реліз затримався на рік), з'явився однойменний дебютний альбом "Ark", дуже тепло зустрінутий музичними критиками у всьому світі.
Це було вобщем-то дивно, оскільки платівка була дуже різнопланова. Музиканти вирішили поекспериментувати і намішати різних стилів. Динамічний саунд, замішаний на хард-року був розбавлений заплутаними ритмічними зразками з обширною мелодійної структурою. Через два тижні після виходу платівки в скандинавських країнах весь тираж був розкуплений. Наступний альбом записувався в Німеччині в "Area 51 Studios" з продюсером Томмі Ньютоном. "Burn The Sun", що з'явився на світ навесні 2001 року, став значним кроком у музичній творчості групи. Склад "Ark" поповнився відразу двома новими учасниками - басистом Ренді Ковеня (раніше працював зі Стівом Веем і Стівом Морсом) і клавішником Матсом Олоссоном (до того протягом останніх 10 років грав у Інгві Малмстіна). Їх поява внесло додаткову різноманітність в саунд колективу.
Стилістика альбому стала ще більш різноплановою - тут був і прог-хард та психо-метал і арт-психоделія і східні мотиви, ну і звичайно ж ізлюбенний номер - фламенко ("Just A Little"). Тим не менш єднальна нитка все таки, оскільки концепція платівки була присвячена темі збереження універсального балансу нашої планети. Починаючись з ядра Землі, музика ніби розгортається, охоплюючи поступово сушу, море, небо, земні істоти. В кінці 2000 року Ланде і Макалусо встигли трохи взяти участь в команді Інгві Малмстіна. Навесні 2001-го пройшли дуже успішні гастролі "Ark" по Європі і Японії. А влітку 2002-го команда знову зібралася для запису чергового альбому.