Несмотря на все усилия, в районе поиска никаких следов аварии или катастрофы не обнаружили. Поисковые силы, однако, непрерывно наращивались и к середине дня уже насчитывали пять эсминцев, шесть подводных лодок, восемь малых противолодочных кораблей, три тральщика, восемь самолетов Бе-6, семь вертолетов Ми-7 и восемь спасательных судов.
При этом все участвующие в поиске силы были разделены на семь отрядов. 1-й отряд составили эскадренные миноносцы: «Сведущий», «Скромный», «Настойчивый», 2-й отряд — «Гремящий» и «Оживленный», 3-й — подводные лодки, 4-й и 5-й — ПУГи малых противолодочных кораблей. 6-й — тральщики, а 7-й — спасательные суда. В отдельные отряды объединили самолеты и вертолеты. Отряд обеспечения составили танкеры и торпедные катера.
Район поиска непрерывно расширялся. Одновременно проводился опрос экипажей всех проходивших мимо района предполагаемой гибели С-80 судов.
В местах базирования в немедленной готовности к выходу находились спасательное судно «Алдан» с колоколом, способным погружаться на глубину 280 метров, спасательные суда «Памир» и СС-1, спасательный буксир. Поисковые силы возглавил командир эскадры надводных кораблей Северного флота контр-адмирал Аистов, поднявший свой флаг на эсминце «Гремящий». Вместе с ним находился и командир 8-й дивизии подводных лодок контр-адмирал Егоров, который затем перебрался на траулер «Тунец», где и оставался до окончания поисковых работ.
Одновременно на Северном флоте была подготовлена команда лучших водолазов-глубоководников из опытных офицеров и мичманов. Подобные команды сформировали на Балтийском и Черноморском флотах. Водолазы ждали лишь сигнала к началу работ. Для их доставки выделялись самолеты морской транспортной авиации. В Ленинграде в готовности к вылету находилась группа специалистов во главе с начальником аварийно-спасательной службы ВМФ инженером контр-адмиралом Чикером. Из Севастополя в Североморск был доставлен проходивший испытания на Черном море поисковый комплекс «Мизень-2» Из Ленинграда самолетом Ли-2 переправлено пять опытных комплектов телеаппаратуры АПТ-1 («Креветка»).
В 11 часов 10 минут 28 января главнокомандующий ВМФ адмирал Горшков доложил о происшествии секретарю ЦК КПСС Устинову, а в 12 часов 30 минут сделан письменный доклад дежурному генералу Генерального штаба. Тогда же было уточнено, что ракет на борту С-80 не имеется, а экипаж насчитывал 69 человек. Цифра 69 значится в документе, тогда как на самом деле на лодке находилось 68 подводников. И здесь невероятная схожесть с ситуацией на С-117, где по всем документам числятся 52 человека, тогда как пофамильный список содержит почему-то всего пятьдесят одну фамилию.