Piłka nożna po raz pierwszy pojawiła się w mieście w 1911 roku, a po pewnym czasie pod kolejnymi wyznaniami „Deportivo”, „Castalia”, „Gimnástico”, „Cultural” i „Cervantes”, Club Deportivo Castellón został założony 22 lipca 1922.
W sezonie 2004/05 Castellón zajął czwarte miejsce w Segunda B , ostatecznie wygrywając baraże o awans (oba mecze) i powracając do srebrnej kategorii. Klub w dywizji trwałby pięć lat, ponieważ spadłby z ligi w latach 2009–2010 , a strój Wspólnoty Walencji zajął ostatnie miejsce, 13 punktów za następną drużyną.
W dniu 18 lipca 2011 roku, z powodu niepłacenia przez drużynę swoim zawodnikom, Castellón został wykluczony z trzeciej ligi, spadając do czwartej . W czerwcu 2017 roku były zawodnik Pablo Hernández został współwłaścicielem klubu, prowadząc konsorcjum wraz z Angelem Dealbertem , biznesmenem Vicente Montesinosem i innymi.
W dniu 21 marca 2018 r. Castellón pobił rekord biletów sezonowych w czwartej lidze należący wcześniej do Realu Oviedo z liczbą 12 700, ustanawiając nowy rekord na poziomie 12 867. 24 czerwca 2018 roku powrócił do trzeciej ligi po siedmioletniej nieobecności.
26 lipca 2020 roku Castellón awansował z powrotem do drugiej ligi po 10 latach, pokonując Cornellà w ostatnim awansie barażowym, ale natychmiast spadł z ligi w sezonie 2020–21 .