Интенсивная поисковая операция производилась вплоть до 16 февраля, но оказалась безрезультатной. Расчетное время возможного существования людей на борту затонувшей лодки истекло. Поисковые работы начали было уже понемногу свертывать, когда 2 марта спасательное судно СС-21 зацепилось якорем за неизвестный тяжелый предмет, лежащий на дне. Предмет этот оставил на лапе якоря след сурика, которым окрашивали корпуса подводных лодок. Снова последовала серия выходов в море и тщательное обследование «подозрительного» района, но и здесь все оказалось напрасным. Пропавшей субмарины не нашли. Как показали расчеты, к этому времени даже при самом благоприятном развитии ситуации для оказавшихся в подводном плену моряков С-80, из них никто уже не мог остаться в живых. В связи с этим было решено больше не изматывать понапрасну экипажи кораблей и судов, а вернуть их в свои базы. Однако поисковые мероприятия продолжались еще вплоть до августа 1961 года кораблями различных соединений по специально разработанному плану штаба Северного флота.
Год за годом корабли в какой уже раз обследовали район предполагаемой гибели С-80. Один раз был даже обнаружен лежащий на глубине двухсот сорока метров неизвестный танкер. С новой силой работы возобновились в 1965 году. При этом использовалась вся новейшая аппаратура: гидрографические эхолоты, маг-нитые металлоискатели, специальные гидрологические станции поиска затонувших подводных лодок и телевизионные подводные установки. Так, по плану в 1967 году корабли производили поиск в южной части района, а в следующем, 1968-м, перешли в северную. Настойчивость и последовательность североморцев оказались в конце концов вознаграждены.
23 июля спасательное судно СС-47 в северо-восточной части полигона, где пропала С-80, в точке с координатами: широта 70 градусов 01 минута 23 секунды северная, долгота 35 градусов 35 минут 22 секунды восточная на глубине 196 метров с помощью гидролокационной станции поиска затонувших подводных лодок МГА-6 обнаружило затонувшую подводную лодку.
Первое же визуальное обследование, произведенное с 12 по 20 августа наблюдательными камерами НК-300 и НК-600, показало, что затонувшая подводная лодка и есть пропавшая в 1961 году С-80. Осматривать затонувшую лодку спускался на наблюдательной камере лично первый заместитель командующего Северным флотом вице-адмирал А. И. Петелин. В свете прожектора субмарина являла собой фантастическое и жуткое зрелище.
