Алексей загорелся идеей вывести «Ассоциацию» на сцену. Носить в себе материал, не показывая его зрителям, было больше невозможно, это сильно действовало на нервы. Срочно сочинялись новые песни. Сильно переделывались несколько старых. В условиях жесточайшего цейтнота записали альбом «Клетка для маленьких». «У меня тогда были сильны амбиции, требовалось доказать всем и себе, что я пишу охеренную музыку. Доказал. Я остался очень доволен авторской мыслью, которую вложил в этот альбом. Мне до сих пор дико нравится пятичастная песня „Окрыленные слоны“. Я даже умудрялся петь ее живьем, хотя это невозможно сложное произведение. Там тысячи контрапунктов, пересечений, слияний — в общем, все по-серьезному». Над записью Могилевский работал вместе с Володей Елизаровым, который стал автором песни «Следы». «Это было хорошей школой. Вова тогда научил меня петь».
В начале 1989-го «Ассоциация» отправилась в первую гастрольную поездку в Нижний Тагил. Директор «Студии Наутилус Помпилиус» Виктор Зайцев решил подстраховаться и, заключая договор на концерты, указал в нем не группу с мало кому известным названием, а «Студию НП». Тагильские организаторы на афишах расшифровали: «Студия „Наутилус Помпилиус“». Естественно, зрители, которые пришли на «Нау», были в бешенстве, и Могилевский отгреб свою долю свиста и воплей. Публика хотела слышать «Я хочу быть с тобой» и видеть Бутусова, а им «подсунули» Могилевского и «Ассоциацию».
Больше подобных проколов Алексей старался не допускать. Хотя и позже организаторы концертов пытались на афишах набрать «Наутилус Помпилиус» более крупным шрифтом, чем название его собственного проекта, сам он изо всех сил от подобного «примазывания» открещивался. В репертуаре «Ассоциации» всего одна песня могла напомнить публике о прежнем месте работы части музыкантов. В начале 1987 года Бутусов решил обновить «Наутилусу» кровь и предложил согруппникам сочинить музыку на еще не использованные тексты. Кто-то попробовал, кто-то нет. У Могилевского быстро получилась «Песня в защиту мужчин». Композицию исполнили всего несколько раз — Бутусов не любил чужой материал и плохо его исполнял. В 1989 году Могилевский написал на эту же мелодию свой текст, получилась песня «День Помпеи».
«Ассоциация» разъезжала по Сибири и Уралу. Крупнейшими гастролями в ее жизни стал совместный тур с «Веселыми ребятами» — 28 концертов в городах Казахстана. Выступали на стадионах. Публика принимала хорошо, аплодировала. То, что название «Ассоциация» было мало кому известно, никого не смущало. И у «Веселых ребят» в ту пору почти не было хитов, но люди тогда ходили не на имена, а на событие.
В Павлодаре кто-то из зрителей кинул в «Веселых ребят» бутылку. Те обиделись и, прервав концерт, ушли со сцены. Следующий день у музыкантов был выходной. Утром в дверь Пифы постучались: «Открываю — стоят местные братки: „Извините, вчера такая лажа вышла. Того козла, который бутылку кинул, уже наказали. А теперь поехали с нами на пикник. Будем вину заглаживать“. Я пытался объяснить, что мы не те, в кого бутылку кинули, но они не слушали. Музыканты и музыканты. Отвезли нас на Иртыш, накрыли великолепную поляну, покатали на катерах на подводных крыльях. Кто-то из них съездил за водными лыжами, еще и на водных лыжах покатались. Вернулись в гостиницу мы очень довольные и были согласны, чтобы в „Веселых ребят“ бросали бутылками хоть на каждом концерте».
В конце весны Шавкунов, разрывавшийся между «Ассоциацией» и «Настей», сделал выбор в пользу девушки. В группу Могилевского пришел молодой басист Слава Двинин. В октябре «Ассоциация» приняла участи в IV фестивале рок-клуба. Их концерт некоторыми ортодоксами классического рока был принят в штыки, но большинство зрителей поняли, что в палитру СРК добавилась новая яркая краска. В декабре группа с успехом выступила в Москве на фестивале «Звуковой дорожки» газеты «Московский комсомолец». В 1990 году «Клетку для маленьких» выпустила на виниле фирма «Мелодия», что добавило «Ассоциации» популярности. Продолжались концерты и усиленные репетиции. По словам Пифы, «в „Ассоциации“ мы уже были взрослее, чем в „Наутилусе“, и гораздо опытнее, поэтому процесс творчества проходил профессиональнее, но и чуть-чуть скучнее».