De club werd opgericht als Club Deportivo Los Náuticos in 1972. De club speelde in lagere reeksen. In 1992 werd de naam Club de Deportes Talcahuano aangenomen. In 1999 werd de club kampioen en promoveerde zo voor het eerst naar de Primera B. Op 27 maart 2004 nam de club de huidige naam aan ter nagedachtenis van Deportes Naval, dat in 1991 ontbonden was. In 2005 volgde echter een degradatie naar de derde klasse. De club kon van 2009 tot 2014 terugkeren.