It all began courtesy of two Scots, Alexander Mackay and Robert Russell Ross, overseas workers at the Rio Tintomines, and the club was originally named Huelva Recreation Club. The doctors founded a recreation club in order to provide the mine workers under their care with physical recreation. Then they were invited by Sevilla F.C. to play their first football match.
Recre would play again in the first division in 2002–03, in another short-lived experience. However, it achieved one of the most significant honours in the club's history by reaching the final of the domestic cup for the first time, being defeated by RCD Mallorca 0–3. In 2005–06, after beating CD Numancia on 4 June 2006, it mathematically secured promotion with two matches left to be played.
"Everything in life has a beginning and an end, and this is the moment to end my time at Recre," Marcelino told a news conference.
This fueled speculation in June 2007 that Recreativo had offered Danish legend Michael Laudrup a contract to coach the club in 2007–08. According to Laudrup's agent, the negotiations were ongoing and "very serious." However, Laudrup turned down the offer, and took the vacant manager's job at Getafe CF in July 2007. Recre' season was a rocky one, as they only achieved to maintain first division status in the very last matchday, drawing with Real Valladolid 1–1. Also, Mallorca's 3–2 success against Real Zaragoza, contributed to Huelva's final 16th position.
In 2008–09, Recreativo de Huelva lived in the mid-table regions for the vast majority of the campaign. However, after just one win in its last 15 matches (this included losing the last four) and one draw, it was finally relegated back, ranking last.