La unua mencio de la nomo “Valdaj” troviĝas en la betulŝela dokumento № 740, kiun oni datas de 1140–1160. En la dokumento, verŝajne, oni skribas pri imposto de Valdaj, eble temas pri la tuta regiono apud la samnoma lago.[1] Unuafoje sendube la loĝlokon oni mencias en kronikoj ĉe la jaro 1495. Ekde 1770 Valdaj havas statuson de urbo.[2]
Valdaj situis ĉe la vojo inter ambaŭ rusiaj ĉefurboj, la malnova kaj la nova: Moskvo kaj Sankt-Peterburgo. Faritaj en Valdaj sonoriletoj estis famaj en tuta Rusio. Nun en la urbo ekzistas la muzeo de sonoriloj (kaj sonoriletoj), kaj ĝis nun la plej ordinara memoraĵo, kiun oni aĉetas dum vizito en la urbo estas sonorileto.
En la urbo estas fervoja stacio. En jaro 1959 la urbo havis 10.6 mil loĝantojn. En jaro 2002 la urbo havis 18.7 mil loĝantojn.