El castillo de Villar de Leche o de Valdemedina fue construido en la Alta Edad Media, si bien en el emplazamiento en el que se asienta se han llegado a encontrar restos romanos y visigodos.
No obstante, en lo que concierne a la fortaleza propiamente dicha, se trata de un castillo construido en el siglo VIII por el Emirato de Córdoba, que fue tomado en el siglo X por el rey Ramiro II de León, acometiendo los sucesivos monarcas leoneses diversas reformas en dicho castillo hasta el siglo XIII, reformas a las que debe su imagen actual.
Por otro lado, cabe señalar que desde el siglo X formó parte del entramado defensivo del Reino de León en su avance hacia el sur en la Reconquista, así como en la defensa de las posiciones de dicho reino en el entorno del río Alagón y la sierra de las Quilamas.
Se accede al torreón del castillo mediante un arco ojival o apuntado que aún se conserva en buenas condiciones.
Se encuentra en estado de abandono y ruina progresiva, con gran parte de la estructura ya derruida y con riesgo de sufrir nuevos derrumbes en la parte del castillo que se conserva, especialmente en su parte más alta.