Состав коллектива неоднократно менялся. Изменениям подвергался также и музыкальный стиль группы. Так, в начальном периоде «Наутилус» играл хард-рок, а во время популярности коллектива в середине 1980-х годов основным жанром являлась новая волна; также творчество группы пересекается со многими направлениями рок-музыки — альтернативный рок, постпанк, готик-рок, арт-рок, симфо-рок, глэм-рок, инди-рок, фолк-рок.

Появление группы «Nautilus Pompilius» уходит своими корнями в 1978 год, когда «на картошке» состоялось знакомство студентов Свердловского архитектурного института Вячеслава Бутусова и Дмитрия Умецкого. Там у них появилось желание создать рок-группу. Как и другие студенты, Бутусов и Умецкий собирали корнеплоды в селе Мамино. Помимо встречи с Бутусовым, Дмитрий Умецкий познакомился и с барабанщиком Игорем Гончаровым, который уже выступал на танцевальных площадках в Челябинске. В колхозе Умецкий и Гончаров поделили музыкальные инструменты: Гончарову достались барабаны, а Умецкому — бас. Однако Вячеслав Бутусов учился в другой группе и занимался музыкой самостоятельно. Сошлись трое студентов лишь на втором курсе.

6 июня 1981 года в ДК «Автомобилист» прошёл городской рок-фестиваль на приз САИ. Увиденное произвело на Бутусова и Умецкого сильное впечатление. Так, например Дмитрия Умецкого удивила рок-группа «Трек»: «Мы поняли, что если так могут петь люди, живущие на соседних улицах, то значит и мы способны на что-то подобное». Вячеслав Бутусов для газеты «Архитектор» взял интервью у Александра Пантыкина и Анастасии Полевой. Студенты предприняли попытки сотрудничества с профессиональными музыкантами. Для этого они обратились к Евгению Писаку, которому предложили быть их лидер-гитаристом. Во время репетиции возникали проблемы с ударником: нельзя так просто составить программу из одних и тех же медленных песен.

Период 1987 года стал одним из успешных в истории группы. Фестивальные выступления и активное участие преимущественно имели оглушительный успех. Первый удачный концерт был проведён 4 апреля в Ленинградском дворце молодёжи перед жюри из Союза композиторов. Публика, присутствовавшая на выступлении, высоко оценила творчество группы. 28 апреля «Советская культура» выпустила «разгромную» статью, обеспечив группе всесоюзную известность. Успех коллектива был подкреплён выступлениями на фестивалях «Литуаника-87» в Вильнюсе 23-24 мая, в подмосковном Подольске 12 сентября. 3 мая группа впервые исполнила песню «Я хочу быть с тобой» — один из главных хитов группы. В связи с призывом в армию 7 июля уходит барабанщик Альберт Потапкин. Последний концерт с его участием прошёл 27-28 июня в Черноголовке. Лишившись ударных инструментов, «Наутилус» некоторое время выступал с драм-машиной. Начиная с сентября вместо ушедшего Альберта Потапкина барабанщиком стал Владимир «Зема» Назимов. 10 октября «Nautilus Pompilius» впервые выступает в Москве в ДК имени Горбунова и 10 декабря на «Рок-Панораме-87». Появились публикации в центральной прессе (первая журнальная публикация — в органе ЦК ВЛКСМ «Смена» (№ 7, апрель 1988), статья Евгения Додолева «Наутилус или Pompilius?»). В конце 1987 года группа уволила звукорежиссёра Андрея Макарова. Заменил его грамотный звукооператор Владимир Елизаров.

К 1988 году «Наутилус Помпилиус» становится одной из известных рок-групп страны, составляя конкуренцию таким коллективам, как: «ДДТ», «Аквариум» и «Кино». Популярность группы отчасти была обусловлена её участием в программе «Взгляд». Сергей Ломакин в газете «Музыкальная правда» вспоминал « «Взгляд» эксплуатировал закономерный интерес публики к социальному року. И показал массовой публике лучшие команды: ДДТ, «Наутилус Помпилиус», «Кино». Это была настоящая гражданская поэзия, и мы пробили этой музыкой брешь в цензурной стене. Параллельно с нами и с нашей помощью на музыкальные площадки страны прорывались подпольные музыканты. На т.н. «большой» планёрке в Останкино один из музыкальных редакторов однажды сказал: «Огромное спасибо «Взгляду» за то, что он открыл стране советский рок». Бутусов, Цой, Шевчук — это литература неравнодушных людей. Тогда музыка делала революцию… » Первый распад группы

Параллельно с ростом популярности в группе начали возникать творческие разногласия: большое количество концертов, коммерческий успех, неблагоприятная обстановка в советском рок-сообществе негативно сказывались на отношениях внутри группы. Дмитрий Умецкий считал, что коллективу необходимо прекратить концертную деятельность, сосредоточившись на создании творческих идей и потенциала, однако его предложение не нашло поддержки среди остальных музыкантов. В начале февраля бас-гитарист предъявил ультиматум: если группа не прекратит концертную деятельность и не переедет в Москву, то он выйдет из состава. Несмотря на его заявление, остальные музыканты проголосовали за продолжение проведения концертов, в результате чего Умецкий покинул «Наутилус». Для проведения концерта в Химках в качестве бас-гитариста был временно вызван звукорежиссёр Владимир Елизаров. В феврале группа записывает альбом «Князь тишины» в студии Александр Кальянова. Предполагалось, что выпуском нового материала займётся «Sintez Records», однако возникли сложности: заводы отказывались производить продукцию кооперативов, а фирма «Мелодия» мешала планам новых конкурентов, и «Князь тишины» был выпущен лишь в 1989 году. Виктор Алавацкий в 1988 году будет бас-гитаристом «Наутилуса» вплоть до его первого распада, а также станет одним из основателей «Студии НП»

Для того, чтобы не было необходимости прекращать гастрольную деятельность, летом «НП» предпринял попытку записать концертный альбом. В него вошли песни, созданные после выхода «Разлуки», и которые по той или иной причине не вошли в «Князя Тишины». Студия «Sintez Records», возглавляемая Александром Кутиковым, записала выступление группы на многоканальный магнитофон, но звукооператор Владимир Елизаров остался недоволен сведением. Во время проходивших в августе концертов в ГЦКЗ «Россия» многие поклонники начали уходить из зала. В сентябре проходят первые зарубежные выступления «Nautilus Pompilius» в Финляндии, которые в основном были в кинотеатрах перед показом фильма «Серп и гитара». Вопреки неуверенности организаторов, 14-16 октября на третьем фестивале Свердловского рок-клуба проходит последний концерт «Наутилуса». Осознав несовместимость российского шоу-бизнеса и коллектива, 22 ноября Вячеслав Бутусов объявил о роспуске группы, однако после распада музыканты не бросили творческую деятельность. Так, Виктор «Пифа» Комаров, Владимир Назимов, а также гитарист Николай Петров вошли в состав «Ассоциации», организованной Алексеем Могилёвским. Владимир Елизаров, Алексей Хоменко и Виктор Алавацкий сформировали группу «Внуки Энгельса» и создали «Студию НП», в которой были записаны альбомы многих свердловских рок-групп. Человек без имени

Зимой 1989 года Вячеслав Бутусов и Дмитрий Умецкий восстановили отношения и встретились дома у Елены Аникиной. Обоим необходимо было единство, поэтому они назначили друг друга «художественным руководителем» (Дмитрий Умецкий) и «музыкальным руководителем» (Вячеслав Бутусов). В ходе разговоров двое отцов-основателей «НП» обсудили новый альбом и, по достигнутым решениям, стали его записывать. Однако им чувствовалось, что чего-то не хватает. Для этого они пригласили Александра Пантыкина. Раздобыв клавиши, Пантыкин уехал в Москву, откуда был вывезен на дачу, где жили Бутусов и Умецкий. Дмитрий Умецкий был занят организаторской деятельностью: он ездил в Москву, где договаривался с спонсорами. Ему не нравилось то, что на документах желали видеть Вячеслава Бутусова, а в это время Вячеслав Бутусов с Александром Пантыкиным записывали черновую запись нового альбома. К ним приезжал Умецкий и делал выводы, что при участии Пантыкина из «Наутилуса» может получится «Урфин Джюс». Переписывались тексты и музыка. Каждая песня практически была сделана в десять вариантов, однако несмотря на то, что Вячеславу Бутусову нравилось работать с Пантыкиным, Дмитрий Умецкий наоборот не одобрял их деятельность. В конце концов «НП» отказался от Пантыкина. Весной «Наутилус» переехал в Коломяги. Дмитрий Умецкий нашёл новую администрацию для коллектива, а центр научно-технического творчества молодёжи «Эврика» оформил товарный знак «Nautilus Pompilius» и выделил аппаратуру для музыкантов на сумму 75 000 рублей. Начинается работа над кинопроектом «Человек без имени», режиссёром которым стал Виктор Титов, известный по таким фильмам, как «Здравствуйте, я ваша тётя!» и «Жизнь Клима Самгина». Начинается показ программой «A» клипа на песню «Боксёр» и появляется интервью Артемия Троицкого у Вячеслава Бутусова, Дмитрия Умецкого и Елены Аникиной.

Осенью начинается запись альбома «Человек без имени» при участии Александра Беляева, Игоря Доценко и Игоря Джавад-Заде. В ноябре Вячеславу Бутусову, Илье Кормильцеву и Дмитрию Умецкому была присуждена Премия Ленинского комсомола. Илья Кормильцев и Вячеслав Бутусов отказались от неё из-за идеологических соображений. «Так же, как и Илья, я не вижу логики в таких награждениях, и, думаю, премия была присуждена благодаря настойчивости отдельных комсомольских работников.» — ответил Вячеслав Бутусов газете «Аргументы и факты». Дмитрий Умецкий на вручение явился и премию получил. После окончании 4 декабря записи альбома «Человек без имени» на студии «Ленфильм» Дмитрий Умецкий забрал фонограмму себе, и связи между двумя отцами-основателями «Nautilus Pompilius» снова были прерваны. В «Комсомольской правде» появилась информация о том, что после прекращения дружественных отношений между основателями «Наутилуса» будет выпущен альбом «Человек без имени», однако этот материал будет выпущен лишь в ноябре 1995 года. Дмитрий Умецкий предпринял попытки отстоять право на название «Nautilus Pompilius» через суд. Помимо Умецкого, претензии имел и НТТМ «Эврика», который требовал возвращения аппаратуры, выделенной для записи. Однако Вячеслав Бутусов продолжил выступать под названием «Nautilus Pompilius. Новый состав Новый состав группы в 1990 году. Игорь Джавад-Заде, Гога Копылов, Александр Беляев, Егор Белкин, Олег Сакмаров, Вячеслав Бутусов, Пётр Акимов В январе 1990 года Вячеслав Бутусов собирает новый состав группы, в который вошли: Гога Копылов (экс-Петля Нестерова), Игорь Джавад-Заде (экс-Арсенал), Александр Беляев (экс-Телевизор). «Наутилус» за это время уже успел отрепетировать полдесятка композиций. Дебют обновлённого состава состоялось на рок-фестивале «Голубой воробей», проходивший в Восточном Берлине. Первоначально лидер «НП» не хотел ехать на выступление, считая, что песни не до конца отрепетированы, но остальные музыканты сумели убедить его и отправились в Берлин. На фестивале «Наутилус» сыграл четыре песни. На последней у Беляева порвалась струна и коллективу пришлось композицию отыгрывать без него.

По просьбе Вячеслава Бутусова в июне был вовлечён Егор Белкин. Лидер «Наутилуса» думал, что при помощи ещё одного гитариста ему удастся усилить коллектив. 29 июня «Nautilus Pompilius» выступает вместе с «АукцЫоном» и «Поп-механикой» на фестивале «Dawai Rock 'n' Roll», проходивший в Западном Берлине, Ганновере, Гессене, Касселле. 18 июля состоялся концерт «Наутилуса» в Нью-Йорке в клубе «Kenny's Castaways» в программе «New Musical Seminar», показанный по MTV. На следующий день коллектив был приглашён выступить в клубе бывшего менеджера «The Yardbirds», в котором собралось не менее 150 зрителей, большую часть которую из них составляли представители советской миссии в ООН. После возвращения домой «НП» запланировал записать альбом. После ряда неудачных попыток записать альбом на студии «LRO Music», осенью начал распространятся магнитоальбом «Наугад», состоящий из концертных записей в Москве и в Ленинграде. Чуть позже в студии на Фонтанке была осуществлена запись, основа которой послужила для альбома «Родившийся в эту ночь», вышедший лишь в 1991 году из-за нестабильной экономической ситуации внутри России. Пётр Акимов и Олег Сакмаров вошли в состав «Nautilus Pompilius».

Из-за финансового положения в начале 1991 года из группы выходит Игорь Джавад-Заде. Для коллектива это было серьёзной потерей. Последние выступления с участием барабанщика Игоря Джавад-Заде прошли в конце февраля в Казани. Перед его уходом Вячеслав Бутусов вспомнил о вернувшимся из армии Альберте Потапкине. Потапкин встретился с группой в Перми и, будучи на концерте, был в недоумении после проигранного выступления. Пауза между концертами составила десять дней. За это время Альберт Потапкин успел выучить 22 песни. 8 марта Потапкин снова дебютировал в составе «Nautilus Pompilius». В апреле группа приняла участие в благотворительных акциях, среди которых «Рок против террора» и выступление в Минске в рамках поддержки жертв аварии на Чернобыльской АЭС. Пётр Акимов, который не подходил «Наутилусу», перестал участвовать в его концертах. Летом директор группы Игорь Воеводин провёл переговоры с ВПТО «Видеофильм» о записи нового материала], и в результате чего состоялась запись альбома «Чужая земля», который вышел осенью 1992 года. Песни «На берегу безымянной реки» и «Прогулки по воде» стали новыми известными песнями группы, наравне с «Я хочу быть с тобой» и «Скованными одной цепью». В начале лета «Наутилус» отыгрывает концерт, приуроченный к выходу «Родившегося в эту ночь», затем группа отказалась от дальнейших выступлений, сосредоточив свои силы на репетиции нового материала. Внутри группы опять начались разногласия, и в результате «Наутилус» покинули гитаристы Егор Белкин и Александр Беляев. Поэтому к записи альбома «Титаник», демо-версия которого была записана годом раньше при участии музыкантов «Аквариума» и получила название «Титаник на Фонтанке», в качестве гитариста был привлечён Вадим Самойлов из «Агаты Кристи», в 1994 году принимавший участие в концертных выступлениях «Наутилуса», совмещая работу в обеих группах. После записи альбома «Титаник» ушёл из состава и Олег Сакмаров, поскольку он был достаточно плотно занят в «Аквариуме». После распада «Наутилуса» Вячеслав Бутусов вместе с Юрием Каспаряном записали саундтрек «НезаконНоРожденный АльХимик доктор Фауст — Пернатый Змей», выпущенный в 1997 году, а в 1998 году вышел первый сольной альбом Вячеслава Бутусова «Овалы», записанный также при участии Олега Сакмарова. Через два года последовали выпуски студийных альбомов Вячеслава Бутусова с разными музыкантами: «Элизобарра-Торр», записанный при участии группы «Deadушки», а также «Звёздный падл», повторяющий опыт «НезаконНоРожденного».