Обеспокоенный надвигающимся штормом, штаб подводных сил передал командиру лодки приказ возвращаться в базу, однако квитанции не получил. Эфир, несмотря на все последующие многочисленные запросы, был пуст. Никому не хотелось верить в худшее. По флоту была немедленно объявлена боевая тревога. Сравнивая ситуацию с исчезновением С-80, нельзя не поразиться ее почти полной схожести с исчезновением С-117. Не менее схоже развивались события и далее.

28 января командующий Северным флотом отдал приказ о начале поисковой операции. В море немедленно вышли эскадренные миноносцы «Гремящий» и «Оживленный», подводные лодки С-46 и Б-36, четыре малых противолодочных корабля, вылетели два самолета Бе-6. Что касается подводной лодки С-46, то она, как и пропавшая без вести С-80, относилась к проекту 644. Перед самым выходом в море командир бригады, который должен был быть старшим на борту, и командир лодки выходить на ней в море наотрез отказались. Оба были немедленно заменены, а затем и сняты со своих должностей. Почему отказались идти в море два достаточно опытных подводника, ведь они прекрасно понимали, что этого отказа им не простят? Скорее всего, дело было в неверии в лодки 644-го проекта, которое после исчезновения С-80 и вызвало такую реакцию. Здесь возникает вопрос: почему командование Северным флотом решило отправить в море именно С-46, когда в готовности к выходу имелось и немало иных лодок? Возможно, такой выбор обусловлен желанием посмотреть на поведение лодки 644-го проекта в море в различных режимах плавания, чтобы попытаться смоделировать ситуацию на С-80, возможно, этот выбор был продиктован стремлением преодолеть у экипажа С-46 естественный психологический барьер, появившийся после гибели «систершипа» их субмарины, а возможно, направили в море то, что оказалось ближе под рукой…

Несмотря на все усилия, в районе поиска никаких следов аварии или катастрофы не обнаружили. Поисковые силы, однако, непрерывно наращивались и к середине дня уже насчитывали пять эсминцев, шесть подводных лодок, восемь малых противолодочных кораблей, три тральщика, восемь самолетов Бе-6, семь вертслетов Ми-7 и восемь спасательных судов.

При этом все участвующие в поиске силы были разделены на семь отрядов. 1-й отряд составили эскадренные миноносцы: «Сведущий», «Скромный», «Настойчивый», 2-й отряд — «Гремящий» и «Оживленный», 3-й — подводные лодки, 4-й и 5-й — ПУГи малых противолодочных кораблей, 6-й — тральщики, а 7-й — спасательные суда. В отдельные отряды объединили самолеты и вертолеты. Отряд обеспечения составили танкеры и торпедные катера. Район поиска непрерывно расширялся. Одновременно проводился опрос экипажей всех судов, проходивших мимо района предполагаемой гибели С-80.

В местах базирования в немедленной готовности к выходу находились спасательное судно «Алдан» с колоколом, способным погружаться на глубину 280 метров, спасательные суда «Памир» и СС-1, спасательный буксир. Поисковые силы возглавил командир эскадры надводных кораблей Северного флота контр-адмирал Аистов, поднявший свой флаг на эсминце «Гремящий». Вместе с ним находился и командир 8-й дивизии подводных лодок контр-адмирал Егоров, который затем перебрался на траулер «Тунец», где и оставался до окончания поисковых работ.

Одновременно на Северном флоте была подготов-, лена команда лучших водолазов-глубоководников из опытных офицеров и мичманов. Подобные команды сформировали на Балтийском и Черноморском флотах. Водолазы ждали лишь сигнала к началу работ. Для их доставки выделялись самолеты морской транспортной авиации.