La temporada 2003-2004 es la primera de Paco Gómez al frente del club. Se juega de nuevo en el grupo III de Segunda división B. A su llegada hace cambios significativos, como son el escudo y el nombre del club, ambos a semejanza del histórico Cartagena Fútbol Club para acercar el club a la ciudad de Cartagena. Machuca fue el primer entrenador de la temporada, después serían Juan Francisco Alcoy (de forma temporal) y Pep Balaguer. Fue una temporada irregular, y solo al final se pudo salvar la categoría con tres victorias consecutivas que dejaron al equipo en la 15ª posición.

En la temporada 2004-2005 el Cartagena cambia otra vez de ubicación para jugar en el grupo IV de Segunda división B. Pepe Balaguer inicia la temporada como entrenador, pero pronto sería destituído por los malos resultados. Vicente Carlos Campillo y Juan Francisco Alcoy aumentaron la nómina de entrenadores de esta temporada, pero el equipo seguía un rumbo irregular. En el último tramo de liga llegó Juan Ignacio Martínez, un técnico que hizo un buen trabajo, salvó al equipo del descenso y mereció la renovación. Al final el Cartagena quedó en 13ª posición.

Tras los últimos fiascos, la afición no esperaba nada nuevo para la temporada 2005-2006. Juan Ignacio Martínez era el entrenador y Paco Gómez puso a su disposición a una gran plantilla a la que debía conjuntar. El resultado fue magnífico, el Cartagena arrasó en el grupo IV de Segunda división B y quedó campeón desplegando un fútbol de superior categoría, siendo un auténtico bloque y modelo a seguir de cómo hacer bien las cosas en esta categoría. El Cartagena se había ganado el derecho a jugar el play-off de ascenso, y era favorito para lograr el objetivo. Sin embargo, a las primeras de cambio el Vecindario eliminó al Cartagena.

En la temporada 2006-2007 el Cartagena intenta seguir la estela del año anterior, el bloque de jugadores es el mismo, y se vuelve a intentar el ascenso de categoría pero sin éxito. David Amaral empezó la temporada como entrenador pero dimitió a mitad de competición, en su lugar vino José Luis Montes pero sería destituído por los malos resultados, y Juan Francisco Alcoy tomó las riendas en las últimas jornadas. La recta final del campeonato dejó al Cartagena fuera de los play-off de ascenso.

La temporada 2007-2008 significa el declive del gran proyecto de ascenso gestado tres años antes. Juan Francisco Alcoy arrancó la temporada en el banquillo manteniendo un buen equilibrio de puntos pero el juego no era nada vistoso y ésto le costo el puesto en una decisión polémica. Pichi Lucas sustituyó al valenciano, obteniendo unos resultados iniciales nefastos que llevaron al Cartagena rozar los puestos de descenso. Sin embargo, una posterior racha de victorias consecutivas llevó al equipo a optar a los puestos de play-off de ascenso, un objetivo al que se llegó a estar muy cerca. Las últimas jornadas del campeonato dejaron sin opciones al Cartagena, empatando muchos partidos en casa, y al final se lograría el octavo lugar en la clasificación.