Valladares were founded in 1923, after a group of men decided to establish a football club in the city.[2] The club entered the Galician Football Federation only in 1950, and played regional football until 1987, whey they achieved their first-ever promotion to Tercera División.
After a short-lived experience in the fourth tier, where they suffered immediate relegation, Valladares returned to the lower leagues until achieving promotion to Tercera Federación in May 2024.[3]