Слава Бутусов учился в соседней группе. Он сам неплохо играл на гитаре, но поначалу предпочитал заниматься музыкой индивидуально. Его однокурсник Александр Коротич вспоминает, как увидел Славу в первый раз: «В общаге на полу сидел очень худой парень с длинной челкой и тренькал на гитаре что-то из „Led Zeppеlin“, явно воображая себя и Плантом, и Пейджем одновременно».
На общей музыкальной почве Бутусов, Умецкий и Гончаров сошлись только на втором курсе. С инструментами помог стройотряд, бойцами которого были будущие рок-звезды, — за 900 рублей купил барабаны и усилители «Эско». Молодежь хотела репетировать в студенческом клубе, но там базировался авторитетный «Змей Горыныч Бэнд». Гончаров договорился о репетиционном помещении в новом общежитии Арха на Восточной, 11. «Всю зиму играли в общаге нечто вроде „кримсонов“, — вспоминал Умецкий, — хотя, честно говоря, „кримсонами“ тут и не пахло. Все это шло еще от одного нашего тогдашнего соучастника, гитариста Сергея Бабушкина, человека явно маниакального склада, рехнувшегося в свое время на „битлах“. А кончилось все это тем, что пришли из комитета комсомола и послали нас всех подальше: нечего, мол, ребята, гнать вам эту лажу». Квартет перебрался в детский садик, где Бабушкин работал сторожем, и продолжил репетировать там. На пианино стал иногда подыгрывать еще один однокурсник, Виктор «Пифа» Комаров. Музицирование шло пока на сугубо любительском уровне.
Что-то изменилось в июне 1981 года, когда прошел городской рок-фестиваль на приз САИ. Бутусов входил в редколлегию стенгазеты «Архитектор», а это издание являлось одной из движущих сил фестиваля. Увиденное 6 июня в ДК «Автомобилист» произвело на Славу и Диму сильное впечатление. Умецкого особенно поразил «Трек»: «Мы поняли, что если так могут петь люди, живущие на соседних улицах, то, значит, и мы способны на что-то подобное. Это было событие, которое перевернуло нашу жизнь». Славе добавили эмоций и два интервью, которые он взял для «Архитектора» у фестивальных героев — Саши Пантыкина и Насти Полевой. «Слава сразу нарисовал дружеский шарж, — вспоминает Настя. — Рассказал, что у него тоже есть группа, что они собираются выступать. Мы подружились».
Чувство, что они сами смогут стать не хуже всех этих «урфинов» и «треков», придало студентам новый импульс. Начались попытки сотрудничества с профессиональными музыкантами. Обратились к гитаристу Евгению Писаку: «Слава с Димой любили „Led Zeppelin“ и хотели вложить их энергетику в свою музыку, подав ее по-своему. Они предложили мне быть их лидер-гитаристом. Слава жил от меня через двор, и мы целыми вечерами сидели у меня, что-то придумывали. Мы не могли двигаться дальше из-за барабанщика. Попробовали одну вещь, другую — не идет. Попытались сыграть медленную — вроде получилось, но нельзя же всю программу строить только из медляков… Я заявил, что нам нужен другой ударник, более ритмичный, собранный, но для них на тот момент дружба была сильнее музыки».
Осенью 1982-го Бутусов — Умецкий — Гончаров с примкнувшим к ним гитаристом-однокурсником Андреем Садновым решили записать собственные сочинения. Семь песен, зафиксированные на пленку Андреем Макаровым, позже разошлись по городу под названием «Али-Баба и сорок разбойников». Создатели остались не очень довольны своим первенцем. «Мы его забекарили сами и лучшие вещи просто объединили со вторым альбомом», — рассказывал Умецкий.
Новый, 1983 год стал для группы по-настоящему стартовым. Коллектив обрел имя — слово «Наутилус» предложил звукорежиссер Андрей Макаров. Бутусов с Умецким, побывав на загородном рок-семинаре, влились в семью свердловских рокеров. Состав изменился: появился барабанщик Александр Зарубин.
В клубе Арха приступили к репетициям новых вещей. Музыку и часть текстов написал Бутусов, а остальные он почерпнул из сборника венгерской поэзии. «Книжка к нам попала случайно, — рассказывал Умецкий. — Просто открыли, смотрим, а там так здорово, у них такие роковые тексты. Эту антологию можно шелушить и шелушить».
Когда в клубе на первом этаже института репетировал «Наутилус», шедевры венгерской поэзии легко можно было разобрать под самой крышей здания. Как-то преподаватель марксистко-ленинской эстетики Олег Петров спросил Бутусова: «Слава, зачем вы так кричите?» — «Я так вижу!» — «Это я понимаю. А кричите-то вы зачем?» После таких вопросов Славина манера пения стала несколько сдержаннее.