De historie van CDA Navalcarnero in het professionele voetbal is nog niet zo heel erg groot aangezien de club pas ruim 25 jaar na de oprichting in de Tercera División terechtkwam in 1987. Sindsdien speelt de club meestal tegen degradatie, het degradeerde ook enkele keren, behalve in de allerlaatste jaren. Tijdens het seizoen 2004/05 kwam de club zelfs uit in de Segunda División B, maar het degradeerde al na één seizoen door een 19e plaats. In de Tercera División Grupo 7 deed de club vanaf de terugkeer mee om een plaats in de playoffs. In het seizoen 2007/08 werd de club tweede in de competitie en keerde het na de gewonnen playoffs weer terug in de Segunda División B. In 2009 degradeerde de club naar de Tercera División. Na zelfs twee seizoenen afgezakt te zijn in Preferente werd de ploeg tijdens het seizoen 2015/16 derde in de Tercera División. Dankzij de play offs komden ze de promotie afdwingen en vanaf 2016/17 heroverde zij hun plaats in de Segunda División B.
