Fuenlabrada was founded in 1975 as a merge between CF San Esteban and AD Fuenlabrada. The idea came from the mayor of the city, Regino Benítez, who suggested the directors of both clubs can unite their efforts and by this receive a higher municipal grant. In 1986, the team first promoted to Tercera Division. They bounced between that and Segunda Division B for the next 30 years. For the 1997-98 season, the club made infusions of certain amounts of money to hire a new coach Eduardo Caturla and new players in order to get back to Segunda Devisión. However, Fuenlabrada finished only in 9th position in the Segunda División B.
Fuenlabrada played at La Aldehuela before moving into the Estadio Fernando Torres in August 2011, named after a Spanish international forward born in the town but who did not represent the club. The 2016-17 season was quite successful for Fuenlabrada. The club finished in 3rd position in the Segunda División B. In that season Fuenlabrada reached promotion playoffs to Segunda División for the second time in its history. But the club lost both matches 0-1 to CF Villanovense.