Two Scots, Alexander Mackay and Robert Russell Ross, overseas workers at the Rio Tinto mines, founded Huelva Recreation Club to provide their employees with physical recreation. Then they were invited by Sevilla F.C. to play their first football match. Very little is officially reported, being one of the most notable games of the time a knock-out stage in 1896 against Locomotoras Albacete Balón-Pie, precursor of the latter Albacete Balompié, in a national cup championship.
During the 1910s, the club won three non-official Andalusian regional cups, and became the first Spanish side to defeat a Portuguese team, winning against Sporting Clube de Portugal. In 1940, it first reached Segunda División, only lasting however one year and not returning until 1957. Since 1965, the team also began hosting the Trofeo Colombino.
In 1977–78, led by, amongst others, former Real Madrid youth graduate Hipólito Rincón, Recreativo first gained promotion to the top flight. After just one season, it returned to level two, staying there until 1990, the year of a Segunda División B relegation.
In 1999–2000, Recreativo were due to be relegated to the third division, but were redeemed when Atlético Madrid descended into the second and thus their reserves were ejected. With a new stadium and the appointment of Luis Alcaraz as manager, and the club returned to the top flight for the first time in 23 years on 19 May 2002 with a 2–1 home win over fellow Andalusians Xerez CD. After this one season at the top, the team was immediately relegated back. However, in the same campaign, it reached the final of the Copa del Rey for the first time, being defeated by Mallorca 0–3 in Elche.
In 2005–06, after beating Numancia on 4 June 2006, Marcelino García Toral's Recreativo mathematically secured promotion with two matches left to be played. Ahead of the new season, the club bought players including France youth international striker Florent Sinama Pongolle from Liverpool, and young winger Santi Cazorla from Villarreal CF, with a budget of only €15 million. The club finished eighth in the table, at 54 points, a best-ever, and made headlines with a 3–0 win against Real Madrid at the Santiago Bernabéu Stadium. The club's leading goalscorer was Sinama Pongolle with 12 goals to his name, while García Toral left at its conclusion for Racing de Santander.
Recre narrowly avoided relegation the following season, and in 2008–09, one win in its last 15 matches led to it coming in last place and returning to Segunda after three years. Overspending in aim of returning to the top flight led to debts. At the end of the 2014–15 season, the team fell into Segunda B for the first time in 18 years. A year later, the club was nearing extinction due to financial problems.