The club was founded in the 1991 as Agrupación Deportiva Las Ruedas Fuenlabrada and acquired a place in Primera Regional Madrileña. It was renamed Club de Fútbol Naranjo Fuenlabrada in the following year before changing to Club de Fútbol Fuenlabrada B in 1996, but ceased activities in 2004.[1]
Fuenlabrada B returned to an active status only in 2015, being registered in the Tercera de Aficionados, the lowest regional league of the Community of Madrid and eighth tier of Spanish football.[2] The club achieved three back-to-back promotions straight to Preferente de Madrid, being relegated in their first season but immediately bouncing back.[3]
On 6 July 2021, after Fuenlabrada bought out the place of Flat Earth FC, the latter club was renamed CF Fuenlabrada Promesas Madrid 2021 and took their place in Tercera División RFEF, while Fuenlabrada B became the second reserve team and remained in the Preferente category.[4]