У тінейджерською віці Стефан зібрав свою першу команду, де експериментував з різними стилями, доходячи до дета і грайндкора. Паралельно він брав уроки гри на гітарі, намагаючись довести свою техніку до майстерності Інгві. Після закінчення музичної академії Форте захопився класикою типу Моцарта і Бартока, а також ф'южн-джазом.
У 1999 році Стефан записав близько десятка композицій і відправив їх на французький лейбл "NTS". Там плівку послухали і запропонували музикантові вигідний контракт, давши можливість зібрати свою власну групу. Першим, до кого звернувся Форте, був український клавішник-віртуоз Віталій Купрій. Хлопці записали разом одне демо, але далі цього справа не зрушила, оскільки Віталій був пов'язаний контрактними зобов'язаннями.
Тоді Стефан вирішив взятися з іншого кінця і знайти вокаліста. Спочатку він хотів запросити в "Adagio" Горана Едман або Томаса Вікстрома, але після зустрічі з Девідом Рідманом з "Pink cream 69" змінив свою думку. Іншими членами команди стали ударник Дірк Брюйненберг ("Elegy"), басист Франк Херманні і клавішник Річард Андерсон ("Majestic"). У такій конфігурації в 2000 році "Adagio" з Деннісом Уордом ("Pink cream 69") в ролі продюсера записали свій перший альбом під назвою "Sanctus Ignis".
На цьому диску Стефан і компанія вдало поєднали класичні елементи з металом, причому в музиці явно простежувалися впливу як великих композиторів типу Бели Бартока, так і сучасних виконавців на зразок Інгві Мальмстіна і "Symphony X". Одним із цікавих моментів "Sanctus Ignis" стала цеппеліновская "Immigrant song".
З часу закінчення сесій першого альбому минуло лише два тижні, як Форте знову почав рватися у бій і приступив до роботи над наступним релізом. На цей подвиг його надихнули твори автора саундтреків до фільмів Джона Вільямса, і він вирішив збагатити звучання "Adagio" оркестровками та хорами. Однак з ходу питання не вирішувалося, і Стефан змушений витратити пару років на вивчення техніки маестро звукових доріжок. За цей час гурт залишив Річардсон, а його місце зайняв Кевін Кодферт. Нарешті, в 2003 році на чолі все з тим же Деннісом Уордом відбулися сесії другого альбому. "Underworld" був виданий японським лейблом "Avalon / Marquee". Завдяки оркестровим аранжуванням диск вийшов набагато сильніше попередника.
Після релізу заявив про свій відхід Брюйненберг, а Херманні запросив на його місце Еріка Лебейллі. За участю нового ударника на початку 2004 року пройшли перші гастролі "Adagio". Згодом на основі паризького і Страсбурзького концертів був випущений диск "A band in Upperworld". Тим часом у колективі розгорівся конфлікт між Рідманом і рештою музикантами. Справа закінчилася відходом вокаліста, а через кілька місяців новим фронтменом "Adagio" став бразилець Гас Монсанто.