En el término de Villalonso se han encontrado fragmentos de mosaicos romanos, lo que parece dar a entender la posible existencia de al menos una villa, aunque la verdadera importancia histórica de la localidad se fraguará en la Edad Media, y se consolidará en la Moderna, en torno a su castillo.

El Señorío de Villalonso surge a finales del siglo XV. Per Yañez de Ulloa, toresano,  de origen gallego, miembro del Consejo de Juan II, fue adquiriendo una serie de propiedades en los alrededores de Toro. Su hijo, Juan de Ulloa,  obtuvo del rey (1449) las antiguas posesiones de la Orden de Alcántara en Pozoantiguo, Benafarces y Villalonso, firmando como señor de Villalonso años después (1470). La familia intervino en las luchas por el poder en Castilla, siendo un hijo partidario de Isabel y otro, de Fernando V de Portugal, quien estuvo refugiado con Juana “La Beltraneja” en el Castillo de Villalonso. Pese a que la fortaleza fue bastión de las Comunidades, el bisnieto de Juan de Ulloa, del mismo nombre, acabará siendo Conde de Villalonso (1599).