Football first appeared in the town in 1911, and after a period of time under the consecutive denominations "Deportivo", "Castalia", "Gimnástico", "Cultural" and "Cervantes", Club Deportivo Castellón was founded on 22 July 1922.
On 29 August 1991, in an extraordinary assembly, the conversion of the club to S.A.D. was approved. The first team had just relegated into division two, and would drop another level to the thirdthree years later, in a spell which would last more than one decade.
In the 2004–05 season, Castellón finished fourth in Segunda B, eventually winning its promotion playoffs (both matches) and achieving a return to the silver category. The club's stint in the division would last five years, as relegation would befall in 2009–10, with the Valencian Community outfit ranking last, 13 points behind the following team.
On 18 July 2011, due to the team not paying its players, Castellón was excluded from the third division, being relegated to the fourth. In June 2017, former player Pablo Hernández became joint owner of the club, leading a consortium alongside Angel Dealbert, businessman Vicente Montesinos and others.
On 21 March 2018, Castellón beat the record of seasonal tickets in the fourth division previously held by Real Oviedo with 12,700, establishing the new record at 12,867. On 24 June 2018, it returned to the third tier after a seven-year absence.
On 26 July 2020, Castellón promoted back to second division after 10 years by beating Cornellà in final play off promotion, but they were immediately relegated in the 2020–21 season.