Одновременно на Северном флоте была подготовлена команда лучших водолазов-глубоководников, в которую входили опытные офицеры и мичманы. Подобные команды сформировали на Балтийском и Черноморском флотах. Водолазы ждали лишь сигнала к началу работ. Для их доставки выделялись самолеты морской транспортной авиации. В Ленинграде в готовности к вылету находилась группа специалистов во главе с начальником аварийно-спасательной службы ВМФ инженером контр-адмиралом Чикером. Из Севастополя в Североморск был доставлен проходивший испытания на Черном море поисковый комплекс «Мизень-2». Из Ленинграда самолетом Ли-2 переправлено пять опытных комплектов телеаппаратуры АПТ-1 («креветка»).

28 января в 11 часов 10 минут Главнокомандующий ВМФ адмирал С.Г. Горшков доложил о происшествии секретарю ЦК КПСС Д.Ф. Устинову, а в 12 часов 30 минут сделал письменный доклад дежурному генералу Генерального штаба. Тогда же было уточнено, что ракет на борту С-80 не имеется, а экипаж насчитывает 69 человек. Цифра 69 значится в документе, тогда как на самом деле на лодке находилось 68 подводников. И здесь невероятная схожесть с ситуацией на С–117, где по всем документам числятся 52 человека, тогда как пофамильный список содержит почему-то пятьдесят одну фамилию.

В 16 часов 40 минут с одного из эскадренных миноносцев доложили: «Есть контакт с большим металлическим предметом на глубине. Широта 69 градусов 48,5 минуты, долгота 36 градусов 20 минут».

В 16 часов 55 минут о контакте доложено главнокомандующему ВМФ. Тот отдает приказ: «Все туда!» Спустя 30 минут контр-адмирал Городницкий доложил об ошибочности контакта.

30 января с подмосковного аэродрома ВМФ Астафьево в Североморск прибыл Маршал Советского Союза К.К. Рокоссовский, бывший в тот период главным инспектором – заместителем министра обороны СССР, Главнокомандующий ВМФ С.Г. Горшков, адмиралы Н.И. Виноградов и Ю.А. Пантелеев и большая группа адмиралов и офицеров центральных учреждений Министерства обороны и ВМФ. Непосредственное расследование происшествия Главнокомандующий ВМФ возложил на своего заместителя вице-адмирала Иванова.

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

Из воспоминаний Героя Советского Союза адмирала флота Г.М. Егорова:

«На совещании, где присутствовали Рокоссовский, Горшков, Чабаненко и другие, я докладывал о состоянии корабля, экипажа и об особенностях управления лодкой с подвешенными на палубу контейнерами после модернизации. Высказал и свое мнение о возможных причинах катастрофы. Что же касается командира корабля, то я дал ему ту оценку, которую неоднократно излагал командующему флотом. В заключение предложил свои соображения по поиску подводной лодки. По моему мнению, в нем должны были принять участие и боевые корабли Северного флота, и суда тралового, рыболовецкого флота, которые имели на вооружении поисковые станции косяков рыбы, способные обнаружить лодку с помощью тралов даже на грунте. Для этого рекомендовал обязательно использовать траулер «Тунец» – специальное поисковое судно полярного научно-исследовательского института главка «Севрыба», имевшее на вооружении современное гидроакустическое оборудование, позволяющее различать не только стаи рыб, но и неровности грунта. Это судно имело опускаемую глубоководную камеру, где мог находиться оператор. По приказанию Маршала Советского Союза К.К. Рокоссовского штаб флота разработал порядок поисковых работ.