За следующие три года «Rock Fuzz» из нерегулярной газетки превратился в ежемесячный журнал, а Леня Фомин стал одним из его руководителей. Между тем и в судьбе группе наметился прогресс: в октябре 1995-го она обрела свое нынешнее название (от латинской пословицы «para pax – para bellum» – «хочешь мира – готовься к войне» или одноименной марки огнестрельного оружия) и первый регулярный состав, в который вошли Глеб Тарабутин, бас, и Александр Сагайтис (экс-ДУКАКИС-PARTY, METAMORPHOSES), барабаны. Глеб, к слову, вскоре тоже стал активным автором журнала. С этого момента PARA BELLUM превратился в реальную группу.
Свой первый концерт PARA BELLUM дал в ноябре 1997 года в клубе «Лесопилка», в рамках небольшого фестиваля при участии групп из Питера, Новосибирска и Бреста. Второй – две недели спустя все в той же «Лесопилке», когда клуб предложил им разогревать публику для культовой гранджевой группы ДЖАН КУ.
В первой половине 1998-го PARA BELLUM дал серию концертов в клубе «Молоко» и в бывшем помещении Ленинградского Рок-клуба на Рубинштейна, 13, как правило, вместе с другими клубными группами, включая ЗАБАВЫ ПРОСТОЛЮДИНА, НЭП, ПЕППИ и т. д.
В начале лета место отправившегося открывать Америку Тарабутина занял опытный музыкант, журналист, знаток и пропагандист гаражного рока и бита Алексей Ершов, в разное время участник групп ЛАВСАН, THE NOIZES, SS-XX, YELLOW PILLOW, UNDERGROUND SUNBURN и т. д. В августе 1998-го группу покинул и Сагайтис, а новым барабанщиком стал Андрей Андрюшко (экс-РЕЗЕРВАЦИЯ). В конце осени Тарабутин вернулся из Штатов на свой пост в PARA BELLUM, а Ершов продолжил популяризацию корневой рок-культуры с YELLOW PILLOW.
К началу 1999-го PARA BELLUM дорос до статуса хэдлайнера концертов в том же «Молоке», а также участвовал в мини-фестивалях на сцене клубов «Полигон» и «Лайза». 24 ноября 1999 года группа презентовала в «Молоке» свой первый междисциплинарный проект: совместную акцию с питерскими художниками Галиной Самариной и Николаем Скрылем, названную ими «Аудиовизуализация Фундаментальных Параметров Сознания». Помимо них участие в акции приняли художники Александр Кляйн (Мюнхен, Германия) и Максимилиан Рецц (Рим, Италия), а также группы MINA и CONTRIVA (Германия).
В декабре 1999-го в рядах PARA BELLUM появился клавишник Степан Славин, параллельно игравший со своей экспериментальной группой VIDNA NEBO. Этот состав в начале января дебютировал в студии «Добролет», впервые записав две своих песни (звукорежиссер Александр Мартисов). Неделей позже группа приняла участие в фестивале «FuzzFest», проходившем под эгидой журнала «Fuzz» на сцене «Юбилейного», где она – помимо собственного материала – исполнила кавер хита Игги Попа «Passenger».
14 апреля 2000 года группа выступила на одной из сцен международного фестиваля Сергея Курехина «S.K.I.F.-4», проходившем в питерском театре «Балтийский дом»; 20 мая отметилась на фестивале «Rocket to Russia» в клубе «Спартак» при участии москвичей Н.А.И.В. и американцев Marky RAMONE & THE INTRUDERS (в рядах последних играл бывший барабанщик THE RAMONES, один из альбомов которых и стал названием всей акции).
В мартовском номере журнала «Fuzz» (2000) был опубликован первый большой материал о PARA BELLUM, а в изданный в том же мае сборник «FuzzBox Vol. 10» была включена их песня «Пять минут любви». Стиль группы в это время все больше смещался в направлении готики, что и послужило причиной первых серьезных разногласий в ее рядах. В июле с PARA BELLUM расстался один из отцов-основателей Алексей Писарев, а его место занял общий приятель, тату-мастер и экс-гитарист группы DEAD MAN (или МЕРТВЕЦ) Тарас Лужецкий. Это, однако, не спасло ситуацию, и в конце сентября PARA BELLUM распался.
Славин и примкнувший к нему Тарабутин продолжали работать как VIDNA NEBO; Андрюшко стал участником группы ТАНКИ, а Новиков начал подыскивать новых музыкантов. Почти сразу на его пути встретился профессиональный гитарист Алексей «Алекс» Шпынев, который во второй половине 80-х прошел через ряды НОКАУТА, СЕЙФА и ЛЕГИОНА, в 90-х был участником СТИЛЯ Сергея Наветного, а также возглавлял группы ОРДЕН и SHRM SOUND. В конце десятилетия он на время покинул музыку, но осенью 1999-го организовал студийную (а позднее и концертную) группу НАМБА ВОН вместе с известным музыкантом, издателем и диджеем радиостанции «Модерн» Геннадием Бачинским (экс-ДЕПУТАТ БАЛТИКИ, ХИМЕРА, «Абдыла Рекордз»).