В музыкальном отношении группа быстро эволюционировала, пытаясь впитать и освоить все, что появлялось у нее на горизонтах: фанк а ля RED HOT CHILI PEPPERS, трэш, панк-металл, глэм-рок, хип-хоп и т. д. Песни удлинялись и усложнялись. «Наша программа подразумевала под собой колоссальную отдачу, потому что песни стали очень сложными, – вспоминает Агеев-Алешин. – Была, например, одна вещь, которая длилась двадцать пять минут и включала около пятидесяти гитарных риффов». Как-то раз PROTOZOA выступили в клубе «10», сыграв за свои сорок минут три песни.
Целый сезон, с осени 1995-го до следующего лета, они репетировали на веранде дачи барабанщика INSIDE Алексея Тенцова, летом отыграли десяток концертов в питерских клубах «10», «Гора» и «Джем», а 13 сентября дебютировали на IV Колпинском рок-фестивале. К тому времени у них была готова неординарная программа из трех песен, одну из которых, «Тень среди теней», музыканты записали для фестивального сборника, позже изданного на кассетах. Публика отнеслась к ним благосклонно, и PROTOZOA, переехав с чужой дачи на тот же Ижорский завод, начали играть в клубах все чаще.
Чувствуя, что ему трудно совмещать игру на гитаре с пением, Агеев-Алешин решил найти для группы вокалиста. За следующий сезон они прослушали два десятка соискателей, ни один из которых не отвечал требованиям PROTOZOA. В 1997-м они сделали еще один заход в студию, записав в клубе «Арт-Клиника» песню «Не заморочен», очередной эксперимент в области смешения стилей, в данном случае хардкора и джаз-рока.
Весной 1997-го поиски голоса наконец-то закончились тем, что к ним пришел Игорь Мамонов. В то время он жил в городке Дно (где отрекся от престола Николай II), хотя до этого колесил по всей стране, а объявление PROTOZOA случайно увидел на стене Пушкинской, 10, и рискнул откликнуться: «Группу, как и все, что происходило тогда в Питере, я до этого совсем не знал, но на первой же репетиции понял, что цели у парней серьезные, а сами они не раздолбаи и не наркоманы. Вот и по сей день вместе».
PROTOZOA
К этому времени на смену многочастным композициям начали приходить более короткие и ударные номера, на которые точно легли голос и тексты Игоря. Группа начала готовиться к новому рывку, но в августе 1997-го окончившего Институт им. Бонч-Бруевича Андрея Агеева-Алешина забрали в армию. Оставив группе демозапись своих гитарных партий, Андрей на два года расстался с коллегами. В его отсутствие PROTOZOA много репетировали, экспериментируя с урезанным составом и модным альтернативным звучанием.
Зимой 1998 года Агеев-Алешин получил отпуск, ввиду чего была устроена запись на студии «Нева» Михаила Кольчугина. Ее итогом стал дебютный мини-альбом из пяти песен, получивший вызывающее название «Дефлорация». Он был издан крохотным тиражом в сотню копий и быстро разлетелся по городу. Появление Мамонова повлияло не только на поэтический язык группы, но и на ее имидж: PROTOZOA начали активно использовать на сцене маски, агрессивный макияж, костюмы и всевозможную бутафорию, тяготея при этом не столько к глэму, сколько к нарочито брутальному гиньолю.
Отслужив два года, Андрей вернулся в ряды повзрослевшей группы. «Когда я вернулся, у ребят было много материала, больше, чем когда я приезжал в отпуск. У меня тоже была масса идей, но кое-что изменилось: у группы появился собственный имидж и манера игры, я уже не мог быть лидером, как раньше, – теперь мне предстояло вписаться в новых PROTOZOA!» В сентябре 1999 года они выступили на фестивале «Поющий Невский» и легко заняли первое место в номинации «Рок-группа».
В начале 2000-го на студии «Сигнал» PROTOZOA записали свой второй, на этот раз полнометражный альбом «Компромат» (звук: Алексей Рацен), в который вошло восемь песен; одна из них, «В горах», была написана на стихи Иосифа Бродского. К работе над альбомом были привлечены и другие музыканты: Таня Яценко и Настя Загорская (бэк-вокал), а также Даниил Прокопьев (перкуссия) из ACKEE WARRIORS; DJ Даня Гагарин добавил кое-где модного скрэтча.
Вскоре послужной список группы начали быстро заполнять новые записи. В марте 2000 года PROTOZOA удачно выступили в МДСТ на фестивале в честь 55-й годовщины Победы в Великой Отечественной войне; в апреле были приглашены на четвертый S.K.I.F.; в мае взяли приз зрительских симпатий на фестивале «Балтийский берег» в Сосновом Бору. Кроме того, они выступали в Выборге, Новгороде и Киришах (фестиваль «Jump!»). В это время группу менеджировала журналистка Елена Вишня.
Материал альбома «Компромат» стал основой саундтрека к документальной ленте «В горах с тобой», который сняла жена Игоря Мамонова Сарра Ансон на Петербургской студии документальных фильмов. Мамонов: «Мы там не играли, мы были самими собой».