Rayo Majadahonda was founded in 1976, being immediately registered in the Madrid Football Federation. It played in the regional divisions until 1987 when it achieved promotion to Tercera División. The club entered this new period with the new president Enrique Vedia, starting from June 30, 1987.[3]
The club established themselves in the fourth division until the 1996–97 campaign, when it achieved a first-ever promotion to Segunda División B. Two consecutive relegations followed, but the club immediately regained their national status in 2000. Then, it subsequently remained in the fourth level until 2015 (only split by a one-season spell in the third division), when it achieved promotion with club legend Antonio Iriondo as manager.
As part of the conditions of playing in the fully professional second division, Rayo Majadahonda had a year to establish a Sociedad Anónima Deportiva, an form of public limited company that all its teams must be. The initial majority shareholder in September 2019 was Alejandro Arribas, a player formed at the club who was still playing professionally for Real Oviedo at the time.[7]
Also in September, 2019 José María Sanz became club's new president.[8]
Founded in 1997, Rayo Majdahonda's reserve team started playing in the Regional Preferente (fifth tier) from 2000 to 2010. It was dissolved in 2011, after a third position in the Primera Regional.
On 4 July 2018, the club reached an agreement with CDF Tres Cantos to become its reserve team.[10] The deal ended in April 2020, when the club announced a link with Alcobendas Sport; the club was renamed CD Paracuellos Antamira.[11]