Els següents deu anys es van romandre a la primera divisió i el descens va ser durar poc, ja que el Valladolid va guanyar una nova promoció el 1958-59 amb un triomf per 5-0 contra el Terrassa sota les ordres de José Luis Saso, figura llegendària de la història del club. Originalment Saso havia estat porter del club i va continuar exercint molts càrrecs, inclosa la presidència del club.
El Valladolid va canviar entre la primera i la segona divisions en anys posteriors, fins que va descendir a la Tercera Divisió la temporada 1970-71. El 1984, el Valladolid va guanyar la Copa de la Lliga (una competició que es va celebrar anualment entre 1982 i 1986) contra l'Atlètic de Madrid.[4]
Ascendit a primera el 1992-93, i hi va romandre fins a la temporada 2003-04. Durant aquest període d'11 anys, la posició més alta assolida per l'equip a primera divisió va ser la setena la 1996-97, sent entrenat en les temporades anteriors per Rafa Benítez.
La temporada 2006-07, després de fitxar l'entrenador bascJosé Luis Mendilibar, el Valladolid va tenir un dels seus millors anys de la seva història al segon nivell. El club va aconseguir el lideratge de la lliga en la quinzena jornada i va finalitzar amb 88 punts, guanyant el campionat amb un marge total de vuit punts i amb un avantatge de 26 punts sobre la zona de no-promoció (quart i inferiors), ambdós registres històrics de la Lliga. El Valladolid també va aconseguir l'honor de mantenir-se invicte durant 29 partits, del 10 d'octubre de 2006 al 6 de maig de 2007, sent ascendit matemàticament després d'una victòria de 2-0 contra el Tenerife el 22 d'abril de 2007 (34a jornada de la temporada), el més primerenc que qualsevol club ha aconseguit la promoció a la història espanyola.[5]
Aquella temporada també va destacar el seu paper en la Copa del Rei, arribant als quarts de final després de derrotar dos equips de primera divisió, el Gimnàstic de Tarragona (4-1) i el Vila-real CF (3-1), jugant tota la competició amb els reserves.
Les dues següents temporades a la primera divisió van ser relativament reeixides, acabant en la 15a plaça, tot evitant el descens després d'un empat per 1-1 en l'última jornada en totes dues temporades (contra el Recreativo de Huelva la 2007-08 i Reial Betis la 2008-09).
Després d'un mal començament en la temporada 2009-10 (3 victòries en els primers 20 partits), Mendilibar va ser destituït l'1 de febrer de 2010 després d'un empat a casa davant l'Almeria. La setmana posterior a la seva destitució, el Valladolid va caure per primera vegada a la zona de descens (cosa que mai havia passat durant els 138 minuts amb Mendilibar), amb l'exjugador Onésimo Sánchez com a entrenador.[6]
Després de només 1 victòria en 10 partits, Sánchez va ser acomiadat. L'exjugador de la selecció espanyola, Javier Clemente, va ser nomenat com a substitut de Sánchez a la desesperada per evitar el descens a falta de vuit partits de campionat.[7] Després de remuntar fins a la 16a posició, el Valladolid va tornar a la zona de descens, i es va plantar a l'ultima jornada havent de guanyar al Camp Nou contra un FC Barcelona que necessitava la victòria per aconseguir el campionat de Lliga. El Valladolid va perdre 0-4 i, per tant, va descendir i va finalitzar una estada de tres anys en el primer nivell.[8]
La temporada 2011-12 va tornar a primera sota les ordres de Miroslav Đukić, aconseguint l'ascens als play-offs després d'acabar tercer en la Segona Divisió.[9] El Valladolid va ser relegat a la Segona Divisió en la darrera jornada de la temporada 2013-14.[10] Quatre anys després, la temporada 2017-18, el Valladolid va tornar a la primera divisió a través del play-off derrotant a l'Sporting de Gijón i el Numància.[11]