Интенсивная поисковая операция производилась вплоть до 16 февраля, но оказалась безрезультатной. Расчетное время возможного существования людей на борту затонувшей лодки истекло. Поисковые работы начали было уже понемногу свертывать, когда 2 марта спасательное судно СС-21 зацепилось якорем за неизвестный тяжелый предмет, лежащий на дне. Предмет этот оставил на лапе якоря след сурика, которым окрашивали корпуса подводных лодок. Снова последовала серия выходов в море и тщательного обследования «подозрительного» района, но и здесь все оказалось напрасным. Пропавшей субмарины не нашли. Как показали расчеты, к этому времени даже при самом благоприятном развитии ситуации для оказавшихся в подводном плену моряков С-80 из них никто уже не мог остаться в живых. В связи с этим было решено больше не изматывать понапрасну экипажи кораблей и судов, а вернуть их в свои базы. Однако поисковые мероприятия продолжались еще вплоть до августа 1961 года кораблями различных соединений по специально разработанному плану штаба Северного флота.

Год за годом корабли в который уже раз обследовали район предполагаемой гибели С-80. Один раз был даже обнаружен лежащий на глубине 240 метров неизвестный танкер. С новой силой работы возобновились в 1965 году. При этом использовалась вся новейшая аппаратура: гидрографические эхолоты, магнитые металлоискатели, специальные гидрологические станции поиска затонувших подводных лодок и телевизионные подводные установки. Так, по плану в 1967 году корабли производили поиск в южной части района, а в 1968-м перешли в северную. Настойчивость и последовательность североморцев были в конце концов вознаграждены.

23 июля спасательное судно СС-47 в северо-восточной части полигона, где пропала С-80, в точке с координатами: северная широта 70 градусов 01 минута 23 секунды, восточная долгота 35 градусов 35 минут 22 секунды на глубине 196 метров с помощью гидролокационной станции поиска затонувших подводных лодок МГА-6 обнаружило затонувшую подводную лодку.

Первое же визуальное обследование, произведенное с 12 по 20 августа наблюдательными камерами НК-300 и НК-600, показало, что затонувшая подводная лодка и есть пропавшая в 1961 году С-80. Осматривать затонувшую лодку спускался на наблюдательной камере лично первый заместитель командующего Северным флотом вице-адмирал А.И. Петелин. В свете прожектора субмарина являла собой фантастическое и жуткое зрелище.

20 августа специалисты по результатам наружного обследования и исходя из внешнего вида подводной лодки сформулировали общую версию гибели С-80. Лодка лежала на грунте без дифферента с креном в 35 градусов на правый борт. Носовая часть слегка задрана вверх. Корпус субмарины был сильно опутан рыбацкими сетями и поплавками. Оба аварийных буя были отданы. РДП (устройство для работы дизеля под водой), антенны и ВАН (выдвижная антенна) подняты в верхнее крайнее положение. Обрастание ракушками и водорослями незначительное. Предварительный вывод сводился к следующему: ракетоносец шел на перископной глубине в режиме РДП, то есть при работающих дизелях, а затем по какой-то причине резко устремился вниз. Возможно, командир внезапно увидел неизвестное судно, шедшее на опасное сближение, и скомандовал «срочное погружение». Поплавковый клапан при этом обледенел и не сработал – вода хлынула в отсеки. Экипаж пытался «продуться» и всплыть, но тщетно. Лодка легла на грунт. Некоторое время люди были еще живы, об этом говорили оба выпущенных аварийных буя.

Позднее государственная комиссия определит причины, почему так долго продолжался поиск пропавшей подводной лодки:

– несовершенство поисковой аппаратуры;

– организация основного поиска в южном районе полигона, там, где был обнаружен аварийный буй.