El nombre «Vitelio» al menos es viejo y se dice que su ascendencia se puede remontar a Fauno, rey de los aborígenes, y a Vitelia.
[1] Entonces, según la tradición, la familia vino de territorio sabino a Roma y fue incluida entre los patricios.
Como evidencia para la existencia de estos reyes tempranos está la Vía Vitelia del Janículo al mar y una colonia Vitelia en territorio ecuo.
Dos hermanos Vitelios están entre los principales seguidores del intento de Tarquinio el Soberbio de recuperar el trono; su hermana era la mujer del cónsul Lucio Junio Bruto.
[2] Por otro lado, Casio Severo y otros consideraron que los Vitelios eran de baja cuna.