International de Madrid was founded in 2002 by a group of businessmen. In its first season, the club joined the Tercera Regional, eighth tier, and played their home games at Orcasitas. Internacional finished its first season achieving the promotion by winning all the games played, scoring 187 goals and conceding only 25.
They achieved a second consecutive promotion in its second season, again leading its group, with 128 goals for and only 17 against.
Internacional de Madrid continued the following seasons playing in Regional Preferente, tier 5. In 2010 they achieved for the first time the promotion to Tercera Divsión by finishing as runners-up of their group.