Параллельно в составе НИЖЕ НУЛЯ происходили определенные изменения: так, осенью 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-го играл на бас-гитаре с возрожденной легендой тяжелого рока, АВГУСТОМ.