Selon
La Petite Grammaire de l'Ancien Français de Bonnard et Régnier :
L'usage de "vos" (vous) comme pluriel de déférence pour désigner un seul destinataire remonte au latin (dès le IIIe siècle). Au Moyen Age, "tu" restait habituel dans les classes "inférieures" ; "vous" s'était répandu dans les classes plus élevées, mais cédait facilement la place à "tu" avec une nuance de mépris ou d'émotion ou sans raison apparente ; dans le Tristan de Béroul, un personnage parlant à son roi passe du pluriel au singulier dans un même vers (1104) :
"Vos estes oncle et il tes niès" (Vous êtes son oncle et lui ton neveu).
J'ajoute ces ref :
Chrétien de Troyes, Yvain le chevalier au Lion vers (euh... vers de vers de poème hein ?! ) 1013 (XIIe siècle) :
"Mes
vos , la vostre grant merci,
M'i onorastes et servistes"
Mais, et je vous en sais beaucoup gré, vous m'y avez honoré et servi
Forme parfois sujette à l'enclise
Béroul, Tristan vers 424 (XIIIe siècle)
"Jos [= Je vos] tien por mon seignor"
Note : la première occurrence de votoier (dire vous en parlant à quelqu'un, vouvoyer) remonte au XIVe.