Fuenlabrada was founded on July 5, 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. A key role in the birth of the new club was played by Ramón García Pajuelo, who was appointed secretary of the entity and is still linked to the club as its delegate. In 1986, the team was first promoted to Tercera Division, finishing third from bottom in their debut campaign.
With Julián Pérez as a president, Fuenlabrada achieved new level, culminating with the promotion to Segunda División B in 1994. 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. With the will to achieve promotion, for the following season the club bet on another coach of recognized prestige and with the experience in La Liga, Felix Barderas.
Fuenlabrada played at La Aldehuela before moving into the Estadio Fernando Torres in August 2011, named after former Spanish international forward Fernando Torres, who was born in the town but never represented the club. In 2016–17, the club finished in 3rd position in Segunda División B, before losing each match of the playoffs 0-1 to CF Villanovense.Mere was appointed as coach for the 2018-19 season.