Посвященный памяти Чумычкина (и включавший две его песни) альбом «Черная метка» АЛИСА записала вчетвером (с клавишной поддержкой В. Осинского в паре песен). В целом это был не самый продуктивный период в биографии популярной группы: она играла довольно невыразительный хард, выступала в небольших залах и пыталась завоевать новую аудиторию среди поклонников КОРРОЗИИ МЕТАЛЛА, гитарист которой, Сергей «Боров» Высокосов, время от времени выступал с АЛИСОЙ на сцене.

Лишь к началу 1996 года, когда АЛИСА выпустила свой лучший альбом 90-х «Джаз», включавший новые версии песен, ранее известных только по соло-концертам Кинчева, кризис был преодолен. «Джаз», в записи которого участвовали Рушан Аюпов (экс-БРИГАДА С, СЕРЬГА), баян, клавишные, бэк-вокал; Сергей Рыженко (экс-ПОСЛЕДНИЙ ШАНС, DDT), скрипка; Сергей Воронов (CROSSROADZ), гармоника, и духовая секция той же БРИГАДЫ С, имел успех как у критиков, так и у публики и открыл новый этап в творчестве группы.

В 1996–1997 годах АЛИСА принимала участие в питерских рок-фестивалях, традиция которых была возрождена «Театром DDT». (Забавно, что во время второго из них на сцене можно было увидеть трех вокалистов группы: Кинчева с АЛИСОЙ, Задерия с его новым проектом MAGNA MATER и Олега Эльтикова с БУРАТИНО.) Помимо этого, она несколько раз подряд собирала полный зал «Юбилейного» на своих сольных концертах.

22 декабря 1996 года в ставшем для группы постоянной концертной площадкой ДС «Юбилейный» состоялась премьера ее очередной программы с достаточно спорным девизом «Рок-н-ролл – это не работа».

В феврале 1997 года состав группы усилил второй гитарист Александр «Панама» Пономарев (p. 4.01.65 в Магадане), бывший участник психоделической группы из Магадана ВОСТОЧНЫЙ СИНДРОМ и бэк-группы Дмитрия Ревякина. В этом составе был записан следующий альбом АЛИСЫ «Дурень» (1997), хитом которого стала песня Кинчева «Трасса Е-95».

В феврале 1998 года группу неожиданно покинул перебравшийся из Москвы в Питер и приглашенный в АКВАРИУМ Пономарев, однако – не менее неожиданно – его место занял еще один петербуржец, гитарист групп НЭП и ДУБЫ-КОЛДУНЫ, а также звукорежиссер Евгений «Лева» Левин (р. 1.03.67 в Ленинграде), дебют которого состоялся на очередном шоу АЛИСЫ в «Юбилейном» 1 мая 1998 г.

11–12 декабря 1998 года АЛИСА отпраздновала в «Юбилейном» свое пятнадцатилетие. В первый день к участникам текущей версии группы на сцене присоединились ее основатели Задерий и Кондратенко (который после ЗАМКА ЗО записывался со студийным дуэтом ХОЛОДНЫЙ ДОЖДЬ, а потом надолго покинул музыку, но не шоу-бизнес).

Летом 1999 года АЛИСА начала работу над новым альбомом «Солнцеворот», материал которого был во многом инспирирован интересом Кинчева к панславизму и языческим корням русской культуры, в чем ранее преуспел его старый друг и единомышленник Дмитрий Ревякин (КАЛИНОВ МОСТ). В процессе записи к группе присоединился следующий питерский музыкант – клавишник и аранжировщик Дмитрий «Ослик» Парфенов (р. 7.11.65 в Москве как Дмитрий Пшишляк), который в разное время играл с множеством групп – от НАРОДНОГО ОПОЛЧЕНИЯ и АУ до ПРЕПИНАКОВ и WINE.

Материал альбома был исполнен на публике 11 декабря 1999 года в «Юбилейном», а сам он вышел в апреле 2000-го, после чего Парфенов был официально зачислен в списки группы (20 мая 2000 г.).

9 февраля 2001 года АЛИСА стала хэдлайнером первого в новом веке питерского фестиваля «Прорыв»; 24 числа того же месяца – после долгого перерыва – встретилась на сцене СКК с DDT и Славой Бутусовым в шоу «Три дороги»; 30 сентября выступила в «Юбилейном» с новой программой «Веранадеждалюбовь», а под Новый год подарила своим почитателям альбом «…Танцевать».