В июле вновь попробовали записаться, и на этот раз успешно. Альбом «Разлука» в клубе архитектурного института записывал Андрей Макаров. Еще в начале сессии стало ясно, что дело пахнет удачей. Могилевский привнес в музыку необходимую долю грамотно поданной танцевальной попсы с хорошим мелодизмом и необходимым хуком. При этом он не давил музыкальным образованием — так, подвинет пальчик Умецкому или посоветует Бутусову остаться не на том аккорде, а на этом. «Именно поэтому я и пришелся ко двору. Пантыкин ведь тоже пытался что-то сделать с „Наутилусом“, но он так дернул одеяло на себя, что архитекторам стало страшно от собственной музыкальной дремучести. А тут вроде тоже музыкант пришел, но он объясняет понятно. А я, видимо, хороший педагог, работал с ними по-простому: делай вот так, парень, и все будет клево. И писалось все влет!»
«Разлука», представленная публике 5 августа, принесла «Наутилусу» уже настоящую славу. Альбом, поначалу далеко не всеми в Свердловске встреченный одобрительно, через несколько месяцев тиражировался тысячами кооперативных студий в не поддающемся исчислению количестве копий. Песни «Наутилуса» вдруг стали символом времени. Все сошлось, как на параде планет, — музыка, тексты, аранжировки, вокал и настроения людей. Все сошлось, и «Наутилус» выстрелил.
Люди желали не только слышать «Наутилус», но и видеть его. Сначала такая возможность представилась только свердловчанам. 5 октября группа появилась перед зрителями в новом облике — в строгих одеяниях, в милитаристских галифе и сапогах, с орденами на бутусовской груди. «Архитектурное образование учит — если не можешь сделать сложно — сделай просто. Двигаться мы не умели, и появилась статика», — объяснял поведение музыкантов Умецкий. В этом имидже, который Дима называл «Врангель на излете», «Наутилус Помпилиус» начал шествие по сердцам поклонников. Уже на первых концертах стало ясно, что для более уверенного марша требуется усилить состав — в живом варианте в музыке зазияли прорехи.
14 декабря на творческой мастерской рок-клуба Слава с Димой обратили внимание на молодого барабанщика группы «РТФ» Алика Потапкина. Сразу после концерта они предложили ему стать «наутилусом». От такой перспективы отказаться было нельзя, и Алик ответил согласием. Однако и «РТФ» он не бросил, целых полгода разрываясь между двумя коллективами.
Уже через несколько дней Потапкин репетировал в клубе Арха: «От волнения и старательности я покраснел как рак и весь трясся. Но ничего, справился. В конце „Буги с косой“ мы с Могилевским выдали джазовую импровизацию. И я почувствовал, что парни-то рассыпались. Тогда Леха скомандовал: „Стоп. Ребята-то джаз играть не умеют“. И мы стали играть поскромнее». 18-летнему студенту музучилища разница в возрасте с остальными казалась огромной, но Слава с Димой безоговорочно приняли его в свой круг общения. И делали все, чтобы Алик чувствовал себя спокойно.
10 января 1987 года состоялись первые официальные гастроли «Наутилуса Помпилиуса». Группа отправилась в Казань. Программа состояла из 14 номеров: это было все, что залитовано, и все, что группа успела отрепетировать. Лес рук, взметнувшийся над залом во время исполнения первых же песен, произвел впечатление на музыкантов — значит, их действительно знают и вдали от Свердловска.
Вылазки в другие города стали почти еженедельными, и возникла проблема. Комаров тогда работал в филармонии человеком-оркестром в программе юмориста Роберта Исакова, концерты которого часто тоже приходились на уик-энды. Требовался второй клавишник. Им стал рок-ветеран Алексей Хоменко: «С моим приходом музыкальная палитра здорово изменилась. Клавиш стало много, но не настолько, чтобы получилось что-то типа „Автографа“».
Именно как секстет «Наутилус Помпилиус» завоевал Советский Союз. Сначала сдались города Урала, затем Поволжье. В апреле случилась безоговорочная победа над Ленинградом, советскими композиторами, собравшимися там на свой пленум, и подрастерявшимся «Аквариумом». 3 мая в свердловском Дворце молодежи впервые прозвучала песня «Я хочу быть с тобой» — хит, с которым «НП» продолжил покорение краев и весей. Пошли рок-фестивали, откуда уральцы неизменно привозили первые призы: Новосибирск, Вильнюс… Это восхождение продолжилось 31 мая триумфом на II фестивале Свердловского рок-клуба, где была показана новая программа «Ни кому ни кабельность». И снова гастроли: Таллин, Черноголовка.
7 июля Потапкина неожиданно призвали в армию. «Наутилус» на полном ходу споткнулся, попробовал выступать под драм-машину, но после живого ударника привыкнуть к механической дуре было невозможно. На одном из концертов техники забыли дать ее отсчет в мониторы, и на «Я хочу быть с тобой» она вылезла в середине куплета. Это барабанщик может подождать. А машина не может. В сентябре позвали за ударную установку Владимира Назимова (экс-«Урфин Джюс», «Чайф» и множество других свердловских проектов).