Весь следующий год НИЖЕ НУЛЯ осваивала сцены питерских клубов: ее охотно привечали «Ten», открывшийся в ноябре 1995‑го «Перевал», принесший им первый успех клуб Политеха (в то время известный как «Лопухи») и т. п. Программа постепенно расширялась за счет своих песен, тексты которых в тот период сочинял в основном старинный знакомый группы Алексей Павлов, из-под пера которого вышел, к примеру, «Пивной блюз». Спустя год после первого концерта появилась идея отметить день рождения трех музыкантов НИЖЕ НУЛЯ (все трое Тельцы по гороскопу) в клубе «Перевал», устроив по этому поводу грандиозный концерт. «Перевал» предоставил место и время, а в качестве гостей выступали ДЕГЕНЕРАТОР, SEVEN HEAVEN и др.

Этот мини-фестиваль открыл целую серию так называемых «concerts for our friends», которые проходили раз в два-три месяца до тех пор, пока в июне 1997‑го «Перевал» не закрылся.

Параллельно в составе НИЖЕ НУЛЯ происходили определенные изменения: так, осенью 1996 года в группе появился клавишник Борис Шнейдерман, однако, отыграв всего несколько концертов, ушел, и она вернулась к классической формуле. С закрытием «Перевала» им пришлось искать новую базу, а заодно и певца, так как Денис Лавренович в силу семейных обстоятельств пересел на скамейку запасных, хотя продолжал подбрасывать группе тексты. Наступали не самые светлые дни.

Группа позвала петь Романа Эламика из THE SHARKS (с которыми позже играл и сам Мурашов), но тогда из этого ничего не вышло. Выход из творческого штопора был найден в июне 1997‑го, когда на очередной репетиции к микрофону была приглашена Анна Морозова. Хотя стиль НИЖЕ НУЛЯ при этом несколько изменился, первоначальной концепции он в целом не противоречил. К концу 1997‑го нашлась и новая база, клуб «Лесопилка» при Лесотехнической академии, где можно было и репетировать, и играть концерты «for friends», к числу участников которых добавились THE SHARKS и ПРОРОК (но отпали, развалившись, МАЛИНОВЫЕ ЗАЙЦЫ).

К 1998 году НИЖЕ НУЛЯ обзавелась достаточно обширным репертуаром и небольшим фан-клубом, а желание непременно улучшать и обогащать звучание заставляло регулярно экспериментировать с приглашенными музыкантами. Так, в 1998‑м в группе некоторое время музицировал (однако так и не прижился) гитарист Денис Димитров.

Все так и шло до тех пор, пока осенью 1998‑го «Лесопилку» не постигла участь «Перевала». Репетиции там еще продолжались, но проводить концерты стало невозможно. Примерно тогда же группу покинула Морозова, хотя она осталась в сфере их интересов. Пару месяцев НИЖЕ НУЛЯ выступала втроем, причем пел в это время Воробьев – в подобной форме группу можно было услышать в ДК «Рыбацкий» и клубе «Космос», где она тогда пыталась закрепиться.

В декабре 1998 года, после повторных переговоров, в НИЖЕ НУЛЯ пришел Роман Эламик из упомянутых выше THE SHARKS. В новом для себя амплуа – хардового вокалиста – он освоился достаточно уверенно, и в феврале 1999‑го группа дала двухчасовой концерт в клубе «Космос». Месяцем раньше НИЖЕ НУЛЯ приступила к записи своей первой демо-ленты. С весны начались регулярные выступления на различных фестивалях в «Полигоне» и еще более частые концерты (нередко сольные) в клубе «Африка». По осени к этому списку добавился клуб «Boom Brazza».

20 ноября 1999 года НИЖЕ НУЛЯ в сессионном варианте (Олег Эльтиков из БУРАТИНО исполнял функции вокалиста) вместе с БРИГАДНЫМ ПОДРЯДОМ, TEQUILAJAZZZ и НЭП выступили на фестивале поклонников «Зенита» в клубе «Малая Охта». Так закончился 1999‑й и прошел 2000‑й. В апреле 2000‑го они отметились на фестивале «Живая культура» и Петроградском рок-фестивале.

В начале 2001 года группу покинул Эламик (а чуть раньше распались THE SHARKS), который ушел в ПРОГУЛ. Его место тут же занял Руслан Матвеев, с 1991‑го и по 1998‑й – вокалист и лидер ДЕГЕНЕРАТОРА. С ним НИЖЕ НУЛЯ закончила репетиции второй программы, хотя так и не сумела записать полновесного альбома. В июле неожиданно закрылась «Африка», и перед группой – уже в который раз – встала необходимость искать крышу над головой.

Только в августе 2001 года они наконец записали первые четыре номера на «RP Studio» Димы Розе, а в конце года добавили к ним еще три, завершив тем самым свой дебютный альбом «Харт». Он был размножен кустарным способом и разошелся по городу, но официально не издавался.

Жилищную проблему удалось решить только к началу следующего года, когда НИЖЕ НУЛЯ перебралась в культурный центр «Евразия» на Лесном (в аккурат напротив «Полигона»), где открыли одноименный клуб и начали устраивать регулярные концерты. В первом из них, 12 января 2002 года, играла сама НИЖЕ НУЛЯ (опять втроем, поскольку в декабре остались без вокалиста, который решил возродить ДЕГЕНЕРАТОР), а также бывший house band «Африки» ВЕРЕСК и молодой ОБЪЕМ 0.5.

К сожалению, «Евразия» просуществовала в форме клуба лишь до 1 мая 2002 года и вновь превратилась в банальное кафе. Тем не менее НИЖЕ НУЛЯ продолжала колесить по клубам, а энергичный Мурашов вместе с экс-вокалистом CONTRA BAND Аланом Лушниковым начиная с апреля параллельно участвовал в группе РАЗРЫВ СВЯЗИ. Осенью НИЖЕ НУЛЯ записала на «RP Studio» сингл «Одной ногой в блюзе».

Весной 2003 года песня НИЖЕ НУЛЯ «Опять за пивом» вошла в сборник «Охота № 8»; сюжет об их восьмилетии был показан по телевизору; в мае они выступили на ежегодном фестивале студенческих групп «Пропеллер‑2003» и на полуфинале «Окон открой!». Вершиной сезона стал для НИЖЕ НУЛЯ концерт на музыкальной ярмарке «MusikMesse» в Ленэкспо, где они играли сразу после РАЗНЫХ ЛЮДЕЙ.

Предыдущие полгода с группой пела вторая в их жизни вокалистка – из Малого оперного театра, но эксперимент был признан неудачным. Мурашов с января по май 2004‑го играл на бас-гитаре с возрожденной легендой тяжелого рока, АВГУСТОМ.

В начале марта 2004 года на «RP Studio» была закончена запись альбома «Лед». Он был отмастерен на студии «Calypso» Алексеем Королевым и той же весной вышел под лэйблом компании «АнТроп». В качестве бонус-трека альбом включал неожиданный кавер «Livin’ la Vida Loca» Рики Мартина. Конец весны группа встретила на фестивале «Балтийский берег» в Сосновом Бору; летом впервые съездила в Москву и презентовала свой альбом в клубе «16 тонн», а позже играла на фестивале «Графские развалины» (Павловск) и на традиционном пивном фестивале в ЦПКиО.

Тем же летом по инициативе Ани Морозовой был снят клип на песню НИЖЕ НУЛЯ «Ведро», который оперативно дали в эфир каналы СТО и СТС.

Поскольку значительная часть раннего репертуара группы так и оставалась на демо-записях, в ноябре 2004 года НИЖЕ НУЛЯ с благословения Андрея Тропилло начала запись своего третьего альбома на его студии. Руководил процессом Сергей Богаев (ОБЛАЧНЫЙ КРАЙ), а сводил запись Виктор Ильин (UNDERGROUND SUNBURN). Альбом получил название «Трое в лодке» (самих музыкантов было трое), но в его записи участвовало множество гостей: Надежда Шинкаренко (MONOSTEREO), флейта; Максим Жупиков (SHERWOOD), скрипка; Эдуард Газизов, саксофон; Григорий Фейгин (ШАМАНАДА), труба; Сергей Макаров, тромбон, а в песне «Слоны» с Мурашовым спела Галина «Гала Роза» Романова (экс-MAGNA MATER).

6 февраля 2005 года в клубе «Red» было отпраздновано десятилетие НИЖЕ НУЛЯ, на котором они впервые выступили с духовой секцией. Там же был презентован альбом «Трое в лодке». За весну и начало лета группа сыграла на открытии байкерского сезона «Весна на колесах», на пивном фестивале, наконец пробилась на гала-концерт «Окон открой!», а также вторично приняла участие в «MusikMesse».

В разгар фестивальной страды о своем уходе заявил Барахтин, и НИЖЕ НУЛЯ начала прослушивать новых барабанщиков. К началу лета кастинг закончился, и в составе группы появился Владислав Мануйлов из ДРУГИХ, который, попав с корабля на бал, дебютировал прямо на стадионе им. Кирова. В начале осени НИЖЕ НУЛЯ снова стала квартетом: к ним присоединилась аккордеонистка Эльнара Шафигуллина – в Питер она приехала учиться с Дальнего Востока и успела отметиться в женской фолк-панк-группе БАБСЛЭЙ. Ее участие заметно изменило общее звучание группы, добавив в него фольклорные интонации.