Новоспечений проект отримав назву "Stoa", у чому відбилося захоплення Паруселя філософією стоїків (stoa - це альтанка де збиралися стоїки).
У тому ж 1991 році фірма "Hyperium" включила пісню дуету до збірки "From Hypnotic ... to Hypersonic". Далі було укладення контракту з цим лейблом, і в 1993-му вийшов перший компакт-диск "Stoa". Дебют виявився відносно вдалим і "Urthona" розійшовся по всьому світу тиражем в 14000 екземплярів.
У 1994 році з'явився другий диск групи, "Porta VIII". Це був вже концептуальний альбом, сюжет якого був побудований як продовження казки Моріса Метерлінка "Аріадна та Синя Борода". За накладом робота також подолала десятитисячного кордон, а, перебравшись через океан, потрапила в мексиканські чарти. На жаль, після виходу "Porta VIII" студійна робота проекту заглухла, основною причиною чого стали погані взаємини з лейблом. Між тим, розпаду групи як такої не було, і в 1996 році її склад поповнився ще однією учасницею, Крістіаном Фішер. Крістіана увійшла до "Stoa" в ролі віолончелістки, а на концертах також виконувала партії бек-вокалу.
У 1997-му в команді відбулася перша заміна: Конні пішла робити класичну кар'єру, а її місце зайняла Антьє Бушхайзер. З досвіду нова фронтвумен не поступалася своїй попередниці - за нею значилося понад одинадцяти років гри на скрипці і спів у класичних хорах типу "Hallenser Madrigalisten".
Однак Антьє не вдалося на повну силу розкрити всі свої здібності в рамках "Stoa". Справа в тому, що в тому ж 1997 році колектив остаточно розірвав відносини з "Hyperium". Всілякі записи з цього моменту припинилися, а виступи групи відбувалися спорадично. Із значних подій кінця 90-х можна відзначити виступ "Stoa" в "Zeche Carl" в Ессені і поява колективу на фестивалі "Wave-Gotik-Treffen". Ще в 1998 році команда зробила турне по Мексиці, висловивши тим самим визнання тамтешньої публіці за "чартового". Початок нового тисячоліття було відзначено заміною основного голосу "Stoa" - ним стала Менді Бернхардт.
Після цієї рокіровки група нарешті приступила до запису довгоочікуваного третього альбому, що отримав назву "Zal". Перший тираж диска був випущений мексиканської фірмою "Samadhi Musik", а після укладення контракту з німецьким лейблом "Alice in ..." з новим творінням "Stoa" змогли ознайомитися і європейці.