Los primeros vestigios del fútbol en el astillero cartagenero datan del 28 de abril de 1922, cuando se funda el Club Deportivo Cartagenero, auspiciado por el mismo astillero departamental, y bajo la protección de la Sociedad Española de Construcciones Navales. Por iniciativa del ingeniero Ulpiano Battle, el primer partido de este equipo será contra el Levante de Murcia. Sus partidos, y los de los diferentes equipos que irán surgiendo a lo largo del tiempo (motores, base de submarinos, forja, máquinas, astilleros, etc.) se jugarán en el campo de fútbol de la Base Naval, hasta la construcción del Campo de Deportes y Recreos de Los Juncos, en 1946.

El Club Deportivo Naval nace en 1943 con el objetivo inicial de representar al astillero de Cartagena en los Campeonatos de España de empresas, siendo su primer nombre el de Consejo Ordenador de las Construcciones Navales Militares (COCNM). El impulsor de este equipo fue el por entonces director de la factoría, Juan Antonio Cerrada y González de Serralde. En su primer año de intervención en el campeonato de empresas, se alzaría con el título de campeón de la zona Alicante-Murcia-Almería, al derrotar al Oliveros SA de Almería. En la fase nacional, el Consejo sería derrotado por la General Gallega de Electricidad. Tras caer eliminado, pasaría a jugar la Copa Consolación, que ganaría tras vencer a Astilleros, de Santander, y al Escoriaza, de Zaragoza, quedando tercer clasificado.

En la segunda temporada en la que participaba el equipo en el Campeonato de España de Empresas, (1944/45) se proclamaría campeón nacional, tras golear 5-0 al Altos Hornos de Sagunto en el antiguo campo de Vallecas, con goles de Lujan(2), Márquez, Paquito y Alcántara. Antes, hubo de batir al Instituto Nacional de Previsión, de Murcia, al Sindicato de la Banca, de Albacete, al Instituto Nacional de Previsión, esta vez de Granada, y en las semifinales a la Sociedad de Pescadores, de Málaga.

En la temporada 1945/46, el objetivo primordial, era revalidar el título, y traer a Cartagena la copa en propiedad, ya que esto se hacía si se conseguía ganar dos años seguidos o tres alternos. El primer rival será la empresa Fernández Requena, de Málaga, y el último, ya que se llegaría a la final otro año más, sería el Segarra, de Castellón, con el que el Consejo perdería 2-0 y se tendría que conformar con el subcampeonato

El buen hacer del Consejo Ordenador de las Construcciones Navales Militares en dicho campeonato, llevó a sus dirigentes a tomar dos decisiones importantes, vitales a la postre. Una, la construcción del Campo de Deportes y Recreos de Los Juncos, inaugurado en julio de 1946, y dos, federar al equipo para que éste compita en categorías regionales, aunque esto se haría efectivo para la temporada 1947/48. Antes, el Consejo Ordenador de las Construcciones Navales Militares, participaría, por último vez, en el campeonato de España de Empresas, para la temporada 1946/47, eliminando en primer término, a un viejo conocido, el Fernández Requena, haciendo lo propio en la siguiente eliminatoria al vencer al Hispano Aviación, de Sevilla. En la fase nacional, los cartageneros vencerían al RENFE, de Ciudad Real, y sucumbirían frente al España Industrial, de Barcelona.

Como decimos, ya se había decidido desde la factoría, federar al equipo para competir en Primera Regional. Y así fue para la temporada 1947/48, el equipo se inscribiría en la Federación Murciana de Fútbol, siendo su primer presidente Juan Antonio Cerrada y González de Serralde. Esto, conllevó un cambio de nombre, que sería Club Deportivo Naval. La primera temporada sería todo un éxito, ya que el equipo conseguiría el ascenso a Tercera División, para la temporada 1948/49.

El debut en Tercera División fue el 12 de septiembre de 1948 ante el SD Sueca en un partido que acabó sin goles, y la primera victoria llegó en la tercera jornada ante el CD Acero por 2-0. El Naval se enfrentó en esta temporada al entonces llamado Cartagena CF, el equipo más potente de la ciudad, deparando una victoria para cada equipo. La temporada terminó con una meritoria sexta posición en un grupo donde había equipos como Albacete Balompié, Elche CF, CD Eldense o el citado Cartagena CF. En esta misma temporada disputó su único partido de la Copa del Rey, por entonces Copa del Generalísimo,^[1]​ y en el que perdió por 0-4 ante el Cartagena CF.

La temporada siguiente, la 49-50, fue la mejor del club logrando un histórico tercer puesto y quedando a cinco puntos de jugar la Fase de Ascenso a Segunda División. En la temporada 50-51 terminó en séptima posición.

En la temporada 51-52 empieza el primer declive del club, el Naval termina penúltimo pero no desciende porque esa temporada no hubo descensos, y en la siguiente temporada 52-53 vuelve a ser penúltimo y tampoco descendió. Tras la temporada 53-54 el club renuncia a su plaza de Tercera División a pesar de ser decimoquinto sobre dieciocho equipos, y tras tres años en Regional el Naval volvió a descender y dejó de competir. El club buscaba otra orientación deportiva más económica y decidió dedicarse a las categorías infantiles y juveniles, convirtiéndose de esta forma en un club de fútbol base durante muchos años.

No fue hasta 1978 cuando el Naval volvió a inscribirse en categoría Regional, para ser exactos Segunda Regional, gracias al convenio de filialidad con el Cartagena FC. Cinco años después se logró de nuevo el ascenso a Tercera División en su grupo XIII exclusivamente con equipos de la Región de Murcia y provincias limítrofes. El Naval quedó noveno en su regreso a Tercera División y dio la sorpresa al llevarse Campeonato de España de Aficionados de 1985, y partir de ahí las siguientes temporadas fueron más discretas en cuanto a clasificación. En la temporada 90-91 el Naval queda penúltimo y desciende a Regional.

En regional se cambió el nombre a Cartagena FC "B" y se volvió a ascender por última vez a Tercera División ese mismo año. Tras una meritoria octava posición en la temporada 92-93, el club terminó descendiendo en 1995 a Regional. Tras varios años en el olvido el club terminó por desaparecer en el año 2002.

El mayor logro del Club Deportivo Naval fue sin duda el Campeonato de España de Aficionados de 1985. El primer equipo, el Cartagena FC ya logró el trofeo en 1978 pero que lo hiciera el Naval fue algo histórico.

Tras quedar campeón regional se enfrentó en primera ronda al CD 501 de Melilla debutando con un contundente 14-1 en el Campo de Los Juncos, suficiente margen para el partido de vuelta que perdió por 4-3. En octavos de final el rival fue el Sporting Mahonés con resultado de 2-0 en Cartagena y otro contundente 1-4 en Mahón. Tocaba cuartos de final y viaje largo para enfrentarse al Artesano de Las Palmas de Gran Canaria; el empate a dos goles en casa dejaba dudas pero el Naval ganó en Canarias 2-3.

El Naval estaba en semifinales y el rival el Sestao SC, empate sin goles en tierras vascas y victoria en casa por 3-2 dieron el pase a la gran final ante el Oviedo Aficionados. Los asturianos se impusieron 3-1 en el partido de ida y parecía muy difícil la gesta, que finalmente se logró con una goleada por 4-1 en un día muy caluroso que influyó en los jugadores visitantes.

En 2013 se fundó el CD Naval Cartagena pero no llegó a cuajar el proyecto. En 2016, nace un nuevo Club Deportivo Naval al amparo de la cantera del FC Cartagena,que a su vez absorbió a la extinta EF Ciudad Jardín. Para la temporada 2024/25, el club solo cuenta con un equipo, inscrito en segunda infantil de la FFRM.^[2]​

• Campeonato de España de Aficionados (1): 1985.

• 4 Ascensos a Tercera División (4): 1948; 1984 y 1992.

• Campeonatos de España de empresas (1): 1945.

• Temporadas en Tercera : 16 temporadas.

• Participaciones en Copa del Rey : 1 temporada.