Founded in 1971 by Dionisio Muñoz Jerez, Alcorcón spent roughly its first 30 years of existence in between the fourth division and the regional leagues. In 2000–01, it made its Segunda División B debut, finishing in 12th place, and spending the following seasons immersed in mid-table positions.
In 2008–09, a third place in the regular season meant Alcorcón was allowed to appear in the promotion play-offs for the first time in its history. After disposing of Sant Andreu and Alcoyano, the club was ousted by Real Unión of Irun in the final round with a 3–1 aggregate scoreline.
On 10 November, in the second leg at the Santiago Bernabéu, the club lost 1–0, but won 4–1 on aggregate, thereby going through to the next round of 16, where the club was ousted by Racing de Santander, 2–3 on aggregate.