The club was founded in 1980 and represents the UAT as well as the city of Ciudad Victoria. It replaced the city's former team, Los Cuerudos, following the team's folding in 1978. The club joined the Segunda División de México in 1982 and played in the 1982–83 tournament. In the 1986–87 tournament the club reached the championship final against the Universidad Autónoma de Querétaro having to play a decisive third game in the Estadio Azteca where the club finally managed to beat Querétaro in a penalty shootout and earning their first Promotion. The club did not fare so well in their first year in the Mexican Primera División finishing tied dead last with Atletico Potosino and only avoided being relegated by a goal difference. Before the 1988–89 tournament the club managed to keep its category after buying the Deportivo Neza Franchisee and taking over their vacant spot. The club would go on to play 7 years in the first division before been relegated in 1995, this time they did not buy any franchise to save their status and instead accepted their fate of playing in the newly created Liga de Ascenso. In the summer 1997 the club reached its first final since joining the league only to lose it to Tigres UANL who would go on to be promoted to the first division having won the previous tournament as well. In the Apertura 2005 and Clausura 2006 the club had one of the strongest teams in the league finishing first in both tournament but losing in the round robin first to León and then to Indios de Ciudad Juárez in semi-finals.
Apertura 2011 Title
In the Apertura 2011 the club finished second in the league with 27 points, 7 wins, 6 draws, 2 defeats, scoring the most goals in the league with 33 and allowing 21 earning a round robin spot. In the Quarter-finals the club faced cross town rival Estudiantes de Altamira who they tied 2–2 after 2 games advancing for having finished with more points. In Semi-finals the club would once again tie 3–3 this time against Toros Neza advancing once again because of their league position. In the final the club would go on to face the league points leader La Piedad who was picked favorite by many to take the Apertura title home that year. The first match was played in the Estadio Marte R. Gómez where Correcaminos managed to take a 3–1 advantage. The second match was played in the Estadio Juan N. López where after 90 minutes the club had managed to beat La Piedad after almost 15 years with a score of 1–0 and claiming that tournaments title.