Pracami kierował Le Vau. Były one prowadzone niezwykle szybko (już w rok po rozpoczęciu prac budowla była zasadniczo wzniesiona, trwały prace przy dachachJ. Cordey, Vaux-le-Vicomte, Paris 1924, s. 39.) i przez dużą liczbę robotników (współcześni badacze nie są zgodni co do ich ilości; podawane są liczby 900J. Cordey, Vaux-le-Vicomte, Paris 1924, s. 35., 5 000J. P. Couchoud, Sztuka francuska, Warszawa 1981, t. I, s. 237. czy nawet 18 000). Ich bardzo wysoki koszt okazał się jeszcze wyższy, niż pierwotnie zakładano.
W 1659 roku pałac odwiedził kardynał Mazarin, co rozpoczęło całą serię wizyt, jakie miały tu miejsce. Miesiąc później gościem był Ludwik XIV. Ponowna wizyta króla miała miejsce w 1660 roku, gdy powracał do Paryża ze świeżo poślubioną Marią Teresą. W 1661 roku w Vaux-le-Vicomte bawiła królowa Anglii Henrietta Maria Burbon, wdowa po Karolu I Stuarcie i jej córka Henrietta Anna z mężem, księciem Orleanu; to wówczas w pałacu swoją nową sztukę Szkoła mężów wystawiał MolierJ. Cordey, Vaux-le-Vicomte, Paris 1924, s. 107-111..