The club was founded in 1957 after Club Refinería Madero folded the year before playing in the Segunda División Profesional, who had previously finished runner-up in 3 occasions first in 1960 behind C.F. Monterrey, second in 1962 behind Club Universidad Nacional, third in 1963 behind 1963. In 1964 the league organized a short playoff tournament in order to increase the number of clubs in the first division. Clubs that took part of the tournament were Nacional de Guadalajara, Tiburones Rojos de Veracruz, Ciudad Madero and Poza Rica. The tournament finished with Nacional de Guadalajara winning the tournament, there was a tie for runner-up between Tiburones Rojos de Veracruz and Ciudad Madero which had to play a final decisive game. That game ended in a 0-0 draw in overtime and so a penalty shootout was the last option. That shootout ended in a 5-4 victory for Tiburones Rojos de Veracruz who along with Nacional de Guadalajara were promoted to the Primera División de México and had the club play its first tournament in the Segunda División Profesional. The club played its first game in the now defunct tournament Copa Mexico as member of the Segunda División Profesional, its first rival was C.F. Monterrey who defeat the club 2-0 matched played in Monterrey, Nuevo León. Their first home game was played on February 27 that same year, losing that match as well 5-1. That same year the club would go on to win its first title just one point over Club Poza Rica who finished runner-up. The club was promoted to the Primera División de México taking over the empty spot left by Nacional de Guadalajara, who had been promoted the previous year. Ciudad Madero became the only team in the world at that time that won the tournament without losing any games – twenty five victories and seven ties under the coaching of Ernesto "Chueco" Candia de Santis, an Argentinian coach that played with Real Madrid from 1948 to 1950. The club made its Primera División de México debut on May 27, 1965, visiting Club Deportivo Guadalajara in a match that ended in a 0-0 draw and earning its first point in the division. The club scored its first goal in the second round against Deportivo Toluca F.C. in the Estadio Tamaulipas and would win its first until the 5th round against Necaxa. The club would finish that tournament 14th overall with 24 points. In the 1966-1967 tournament the club managed to win only one game on the road, which was against Jabatos de Nuevo León, a 1-0 match. The club scored only 8 goals in its 15 games on the road, finishing last in that category. The club finished that tournament in last place with 18 points; the club was mathematically relegated from round 27 when they lost 2-1 against C.F. Monterrey with 11 games left to play. After playing 2 years in the Primera División de México the club returned to the Segunda División Profesional, where they played until 1973, when they once again won the division and earned the right to play in the Primera División de México after defeating Deportivo Irapuato 2-0. The club had a short stay in the top division, playing only 2 years, when in 1975 the club finished last place with 21 points out of 75 possible, 5 points behind the close Club de Fútbol Laguna. The club would not rejoin the Segunda División Profesional due to lack of financial support and would not return until 2002, when the club was reformed as Segunda División Profesional. The club recently plays in the Tercera División de México, where they play out of the XI group.
