Durante la Edad Media Olmillos de Castro quedó integrado en el Reino de León, cuyos monarcas habrían acometido la repoblación de la localidad dentro del proceso repoblador llevado a cabo en la zona, estando vinculado su origen histórico a la fortaleza de Castrotorafe y habiendo dependido de la encomienda de la Orden de Santiago que tenía sede en dicha fortaleza.