К следующему выступлению, которое состоялось 21 декабря в «Fish Fabrique», в составе группы появился тенор-саксофонист Николай Серебряков и название АЭРО-ПЛАН – его предложил Копылков, чтобы хоть как-то обозначить себя в афише. Как бы то ни было, имя прижилось, хотя впоследствии подвергалось разным трансформациям.

В начале следующего года у группы случилась первая гастроль – ее позвали на рок-фестиваль в город Волховстрой, – а на студии «Форум» была записана песня «Дорога». Однако той же весной возникли и первые проблемы: в апреле с АЭРО-ПЛАНОМ расстался Серебряков (позднее в STEREOTYPE и FUN2MASS), а месяц спустя откололся Парыгин, которого пригласили в SPITFIRE. Все лето группа, состав которой пополнил саксофонист Александр Николаев, репетировала в клубе «Wild Side», но концертов не давала.

В конце лета к ним присоединился трубач Олег Соколов (он начинал в MONKEY PUZZLE TREE и пару раз играл с ЛЕНИНГРАДОМ). Олег оказался человеком ненадежным и не всегда адекватным: мог прийти на концерт без трубы или вообще забыть о таковом, поэтому в сентябре в АЭРО-ПЛАН был приглашен еще один музыкант, Константин Колешонок, тенор-саксофон.

31 октября в клубе «Зоопарк» (который надолго стал для них одной из самых привлекательных площадок) АЭРО-ПЛАН отпраздновал свою первую годовщину. На афише к этому концерту впервые появился рисованный биплан, который и стал логотипом группы. В празднике участвовали группа BONIFACY и рок-бард Алексей «Вася» Васильев, школьный приятель Дюши Прокофьева. Вскоре он продал гитару и принял на себя обязанности директора АЭРО-ПЛАНА. Его первой акцией стало их совместное выступление со SPITFIRE в клубе «Малая Охта» 14 ноября 1998 года. Духовая секция группы присутствовала там в полном составе, однако после этого концерта Соколов в АЭРО-ПЛАНЕ не появлялся.

23 января 1999 года АЭРО-ПЛАН снялся для программы новгородского телевидения «Поп-наезд», а неделю спустя на концерте в клубе «City» предъявил публике нового барабанщика: место Лускина, который ушел в FROG LEGS, а еще позже обратился к джазу, занял Алексей «Негатив» Денисов. В конце февраля группа сыграла на мини-фестивале в клубе «Кочегарка» (Выборг), где состоялось ее знакомство с местными панками из П.Т.В.П. и питерской девичьей фолк-панк группой БАБСЛЭЙ. В течение весны и П.Т.В.П., и БАБСЛЭЙ записали на точке у АЭРО-ПЛАНА по альбому (обе работы были приписаны мифической студии «Белоус Рекордз»).

В марте ушел Николаев (позднее ХОРОНЬКО-ОРКЕСТР), но на очередном концерте в «Зоопарке» в ряды АЭРО-ПЛАНА встал трубач Владимир «Тарантино» Морозов, музыкант военного оркестра и бывший участник группы ИНОК. На какое-то время состав стабилизировался, и они начали выезжать на гастроли, в т. ч. два раза подряд играли в Москве. Творческие контакты с БАБСЛЭЕМ незаметно переросли в личные, что повлекло за собой сразу две свадьбы: в августе бас-гитарист Дюша женился на гитаристке Тане Прасс, а певец Коля – на бас-гитаристке Тане Аврамовой.

Двухлетие АЭРО-ПЛАНА в октябре было отмечено концертом в клубе «Молоко» и выпуском нумерованной кассеты «2 года», на которую вошли все десять песен, записанных группой к этому моменту на трех разных студиях. Вскоре после этого АЭРО-ПЛАН в первый раз побывал на рок-фестивале «Nord Session» в карельской Костомукше, где подружился с хардкор-трио ВОЛАНД из Киришей.

В конце зимы группа записала на студии «Нева» новые песни «Рыба Луна» и «Пряточки», а 31 марта организовала в клубе «Сафари» в Выборге фестиваль «В поисках Дурака» (дело было перед выборами президента России), участие в котором приняли П.Т.В.П., ТОРБА-НА-КРУЧЕ, JET и БАБСЛЭЙ. Незадолго до этого, прослышав, что где-то над бескрайними просторами России летает еще один АЭРО-ПЛАН, Кочнев предложил изменить имя группы на НЕАНДЕРБИТ и почти убедил в этом своих коллег. Некоторое время они флиртовали с новым названием, но оно не прижилось, поэтому на вышедшем в мае 2000-го под лэйблом «Manchester Files» дебютном альбоме группы ее название было зафиксировано как АЕРО ПЛАН, а имя «Неандербит» получил сам альбом.