El nuevo club debuta en Preferente con el ascenso a Tercera División y un sexto puesto en la temporada siguiente que hacía creer realmente en posibilidades de alcanzar la añorada Segunda B, pero la temporada 2004-2005 se desciende a categoría Regional Preferente, donde ha militado, exceptuando la temporada 2007-2008 donde el equipo quedó en última posición de la Tercera División y volviendo descender a categoría Regional Preferente.
En la temporada 2012-2013 con Mariano Martínez Tragacete como entrenador, se logra el ascenso a Tercera División tras quedar en segunda posición.
En la temporada 2013-2014 se logra el difícil objetivo permanencia dado que descendían seis equipos, tras una dura temporada el equipo logra la salvación en la jornada 41 tras golear 7-0 al Real Club Deportivo Carabanchel quedando en la decimosexta posición de la liga.
Miguel Ángel Galán presidente de la CENAFE se hace cargo del banquillo y la dirección técnica.
Tras cinco primeras jornadas dimite como entrenador y César Mendiondo se hace cargo del equipo, que hasta la décima jornada no gana su primer partido, lo que viene a ser su peor arranque ligero de la historia.