История «Наутилуса» началась в 1978 году, когда студенты-архитекторы Вячеслав Бутусов (гитара, вокал), Дмитрий Умецкий (бас, вокал), Андрей Саднов (гитара) и Игорь Гончаров (барабаны), создали группу, игравшую на институтских вечерах.

В 1983 возникло название «НАУТИЛУС», которое навсегда закрепилось за группой. В том же году «НАУТИЛУС» при поддержке клавишника и певца «УРФИН ДЖЮСА» Александра Пантыкина и звукорежиссера той же группы Александра «Полковника» Гноевых записала свой дебютный альбом «Переезд», выдержанный в традициях хард-рока. На записи на барабанах играл Александр Зарубин. Тогда же состоялось знакомство Бутусова с текстовиком «УРФИН ДЖЮСА» Ильей Кормильцевым, с которым весной 1984 года они посетили Ленинград, где ознакомились с местной рок-сценой. Результатом поездки стала резкая смена стиля «Наутилуса» — музыка группы стала тяготеть к «новой волне»; нервный вокал Бутусова ярко контрастировал с холодным монотонным аккомпанементом баса и клавишых.

На обложке вышедшего в марте 1985 года альбома «Невидимка» впервые появляется название NAUTILUS POMPILIUS. Группа предстала как «нововолновое» трио в составе: Бутусов, Умецкий и Виктор Комаров (клавишные, ритм-бокс). В июне 1986 NAUTILUS POMPILIUS, в состав которого вошел бывший музыкант «УРФИН ДЖЮСА» Алексей Могилевский (клавишные, саксофон), выступил на 1-м фестивале местного рок-клуба. Месяц спустя вышел их следующий альбом «Разлука» — наиболее известная работа за всю историю группы, получившая небывало широкое распространение по стране.

Популярность группы резко пошла вверх – выступления на подмосковных рок-фестивалях в Черноголовке и Подольске встретили горячий прием у рок-аудитории. В январе 1987 года в группу пришел второй клавишник Алексей Хоменко, а чуть позже барабанщик Альберт Потапкин (экс-«АГАТА КРИСТИ»). В июне Потапкин уходит в армию, и в Черноголовке и Подольске NAUTILUS POMPILIUS снова играл с ритм-боксом, однако с октября за барабанами сидел Владимир Назимов (экс-«УРФИН ДЖЮС», «НАСТЯ», «ЧАЙФ»). В декабре состоялось триумфальное выступление на «Рок-панораме».­ ­

В феврале 1988 года, в результате творческих разногласий, группу покидает Дмитрий Умецкий. Его место занял Виктор Алавацкий, вслед за ним в группе появился бывший гитарист «УРФИН ДЖЮСА» Игорь «Егор» Белкин. NAUTILUS POMPILIUS активно гастролирует по стране и записывает новый материал, часть которого появилась на альбоме «Князь тишины» (1989). В 1988 году режиссер Алексей Хотиненко снял NAUTILUS в своей фантастической ленте «Зеркало для героя». 22 ноября 1988 года Бутусов неожиданно объявил, что распускает группу.

В феврале 1990 года на концерте, посвященном 5-летию Свердловского рок-клуба NAUTILUS POMPILIUS предстал перед публикой в обновленном составе: Беляев, Игорь «Гога» Копылов (экс-«ПЕТЛЯ НЕСТЕРОВА»; бас) и Игорь Джавад-Заде (экс-«АРСЕНАЛ»; барабаны). Вместе с составом изменилось и звучание – основной упор группа делает на характерный для зарубежных «инди»-коллективов минималистский гитарный звук. В мае в группе снова появляется Белкин, с которым NAUTILUS записывает альбом «Наугад». В записи также принимали участие сессионные музыканты Олег Сакмаров («ВЫХОД», ныне «АКВАРИУМ»; флейта) и Петр Акимов («ВЫХОД»; виолончель). В том же году на ленинградском телевидении состоялась премьера кинобиографии группы «Бриллиантовые дороги» (режиссер И. Морозов). Следующие два года прошли в непрерывных гастролях по стране. Джавад-Заде ушел, и за барабаны вернулся Альберт Потапкин.

Осенью 1992 свет увидел альбом «Чужая земля», однако на следующий год после концертов в Калининграде Бутусов неожиданно уволил обоих гитаристов; уже начатая запись нового альбома была приостановлена, а его материал был переписан с лидером «АГАТЫ КРИСТИ» Вадимом Самойловым в качестве продюсера и нового гитариста. Альбом «Титаник» вышел весной 1994 года. Белкин вернулся к собственным проектам; Беляев оставил музыку. Бутусов вновь привлек к участию в NAUTILUS POMPILIUS Алексея Могилевского, новым гитаристом стал участник «АССОЦИАЦИИ» Николай Петров. В этом составе был записан альбом «Крылья».

Осенью 1996 года Бутусов и Кормильцев отправились в Британию, где был записан последний студийный альбом «Яблокитай»: его спродюсировал известный музыкант Билл Нелсон (BE-BOP DELUXE), а в записи участвовали местные сессионные музыканты, но прежде, чем он увидел свет, в январе 1997, Бутусов снова распустил группу.