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