В 1978 году свердловские студенты-архитекторы Вячеслав Бутусов (вокал, гитара) и Дмитрий Умецкий (бас) организовали свой первый совместный музыкальный проект. В 1980 году их детище получило статус рок-группы Свердловского архитектурного института, а в 1982 году - имя Наутилус. Год спустя с помощью звукорежиссёра Александра Пантыкина и поэта-песенника Ильи Кормильцева, известных тогда работой в группе Урфин Джюс, ими был записан демо-альбом "Переезд". К тому времени стиль группы уже можно было определить, как "мрачную волну" (разновидность британского пост-панка) с некоторой ориентацией на творчество Bauhaus, Cure и Damned. Во время концертных выступлений мрачноватая музыка группы дополнялась непривычно строгим обликом музыкантов - минимум движения, строгая чёрно-белая гамма костюмов...

В 1985 году к названию прибавилось Помпилиус: подводную лодку капитана Немо превратили в глубоководного моллюска, дабы избежать путаницы с московской группой Евгения Маргулиса (позже в свою очередь, переименованной в Шанхай), и новый демо-альбом "Невидимка" вышел уже под этим именем. Выступление на фестивале Сведловского рок-клуба и новый, записанный в 1986 году альбом "Разлука" оказались неожиданно удачными и встретили тёплый приём. Именно тогда в репертуаре ансамбля зазвучали такие песни, как "Скованные", "Ален Делон (Взгляд С Экрана)", "Казанова" и "Хлоп-Хлоп". К этому моменту несколько изменилась стилистика - гитары ушли на задний план, а в составе появились Виктор Комаров (клавишные, программирование) и Алексей Могилевский (клавишные, саксофон). Группу заметили и стали приглашать на различные фестивали, что в свою очередь, всё более способствовало росту её популярности. Интенсивная концертная деятельность потребовала расширения состава - в 1987 году в группу пришли второй гитарист Егор Белкин (ех-Урфин Джюс), третий клавишник Алексей Хоменко и "живой" ударник Альберт Потапкин, которого вскоре сменил Владимир Назимов. Весьма удачным было и выступление НП на фестивале "Рок-Панорама-87". А в 1988 году после эпизодического участия группы в кинофильме В. Хотиенко "Зеркало для героя" произошёл прорыв. Ансамбль вырвался на большую сцену, его песни зазвучали по радио и ТВ. В следующем 1989 году единственная тогда в стране звукозаписывающая фирма "Мелодия" издала первый официальный альбом НП "Князь Тишины" - фактически сборник заново переписанных композиций из предыдущих альбомов (предшествовавший ему концертный ЕР, записанный на "Рок-панораме-87" и выпущенный в 1988 году "сплитом" с Бригадой С, вошёл в историю звукозаписи как первый случай выпуска концертного "бутлега" на мейджор-фирме). Во время работы над диском Умецкого сменил Виктор Алавацкий. Во всех тогдашних хит-парадах прочно обосновались антивоенный рок-номер "Шар Цвета Хаки", пронзительная баллада "Я Хочу Быть С Тобой" и эпическая "Гуд Бай, Америка!". Вечно мрачный и таинственный, Бутусов всячески избегал общения с прессой, перпоручив это сперва Умецкому, а затем Кормильцеву, ставшему к тому времени постоянным поэтом ансамбля. Во время концертов музыканты принципиально не выходили на бис, предпочитая один за другим покидать сцену под финальные аккорды "Гуд Бай, Америка!"

К этому моменту вокруг имени группы бушевала самая настоящая истерия, и скандальная история с концертным ЕР хорошо её иллюстрирует. Существование в столь бурной и бестолковой атмосфере не могло не сказаться на благополучии группы. Присуждение ей в 1989 году премии Ленинского комсомола стало жирной точкой, завершившей первый этап её существования - во-первых, от премии НП отказались, а во-вторых, недовольный развернувшейся вокруг группы шумихой и наметившимся творческим кризисом Бутусов ещё в ноябре 1988 года приостановил деятельность коллектива и распустил состав.

Попытки перебравшихся в Ленинград (ныне Санкт-Петербург) Бутусова и Умецкого в 1989 году реформировать группу при содействии гитариста Александра Беляева (ех-Телевизор) и ударника Игоря Доценко (ДДТ) не увенчались успехом по причине творческих разногласий. Окончательно покинувшего группу Умецкого заменил Игорь Копылов (ех-Телевизор, Петля Нестерова), за ударные сел Игорь Джавад-Заде (ех-Арсенал), а в конце 1990 года вернулся в состав Белкин.

Возврат к старому, гитарному звучанию на качественно новом уровне несколько шокировал поклонников ансамбля. Записаный в 1990 году в Западном Берлине альбом "Наугад" (издавался также в несколько иной версии под названием "Родившийся В Эту Ночь") оказался близок по саунду к только лишь "поднимавшим голову" альтернативному гитарному року и гранджу, был фактически принят в штыки и продавался довольно вяло до августа 1991 года, когда группа вновь оказалась в центре внимания в связи с тогдашними политическими событиями. Выступив 22 августа на Дворцовой площади Санкт-Петербурга, НП доказали жизнеспособность нового, более жёсткого и агрессивного звука. Тем же составом год спустя был записан ещё более "готический" и мрачный, несмотря на явное смягчение гитар альбом "Чужая Земля". В этот период список хитов ансамбля пополнили "Тихие Игры", "Падший Ангел", "Прогулки По Воде" и "На Берегу". В записи обоих альбомов принимал участие флейтист группы Б. Гребенщикова Олег Сакмаров. В 1992 году НП и БГ-бэнд провели совместное турне по стране. С этого момента с Бутусовым начинает активно сотрудничать и сам Б. Гребенщиков.

В 1993 году произошла очередная смена состава и стиля - во время записи нового альбома "Титаник" к Бутусову и Копылову вернулся ударник Альберт Потапкин (успевший за время своего отсутствия отслужить в армии и записать пару альбомов с Агатой Кристи), а в новых песнях опять зазвучали клавишные и саксофон - в альбоме их партии исполнял ещё Сакмаров, но уже на последовавших вслед за его выходом концертах в составе вновь появился Алексей Могилевский, до этого с весьма скромным успехом выступавший с собственной группой Ассоциация. Сопродюсером альбома стал гитарист Агаты Кристи Вадим Самойлов. Тем же составом в 1995 году был выпущен альбом "Крылья". Новая, третья по счёту волна популярности, выступление в концертном зале "Россия" с симфоническим оркестром, запись акустического концертного альбома и новые хиты - "Титаник", "Тутанхамон", "Утро Полины", "Дыхание", "Где Твои Крылья?", "Человек На Луне"... Выход ранее нереализованного материала - концертного альбома "Отбой", содержащего несколько оригинальных, записанных лишь на концертах 1988 года, песен - "Падал Тёплый Снег", "Город Братской Любви", "Чужой Человек", "Синоптики" (позже альбом был переиздан в расширенной версии под названием "Ни Кому Ни Кабельность"), забракованной в 1989 году студийной программы "Человек Без Имени", содержащей интересные номера "Боксёр" и "Красные Листья"... И - новый творческий кризис.

Весной 1997 года был выпущен достаточно странный альбом "Яблокитай". Надпись на обложке гласила: "Наутилус Помпилиус: Виртуальная рок-группа". Весь материал альбома был записан на одной из студий Лондона одним Бутусовым. Продюсером альбома выступил Билл Нельсон - бывший гитарист одной из известнейших арт-роковых групп 70-х Be-Bop Deluxe. Несмотря на весьма сильный материал (в хиты вышла почти половина представленных на альбоме песен - "Нежный Вампир" (при участии Б. Гребенщикова), "Девятый Скотч", "Люди На Холме", "Во Время Дождя" и "Апельсиновый День", а сам альбом стал основой саундтрека новорусского боевика "Брат") ансамбль достаточно тяжело принял для концертного исполнения песни, не только созданные, но и записанные одним лишь лидером группы без участия остальных музыкантов, и в конце того же года было объявлено об окончательном роспуске состава.

Вячеслав Бутусов выпустил несколько странных, но интересных сольных работ, а Алексей Могилевский занялся продюссерской деятельностью. Игорь Копылов вошёл в состав группы Ночные Снайперы, Игорь Джавад-Заде работает у Земфиры, а Владимир Назимов - в новой группе Александра Пантыкина.