Siempre el 1 de Mayo se ha ido en romería a algún sitio. Documentado está que en los siglos XII y XIII, se iba andando y descalzos al santuario de Santa María del Monte (en término de Urda), el camino que discurría hasta allí, sigue denominándose “carril del Descalzadero”. Después y, hasta el siglo XIX se hacia una romería en la perdida ermita de Santa Ana, en el camino que hay para Camuñas.

Después, no era una fiesta religiosa, era simplemente, la fiesta del trabajo. Se hacia una romería, quien podía en las sierras, pero no había ningún sitio en particular, simplemente, con ir a comer allí el hornazo, ya se había ido a “Mayo”.

A partir de 1.940, como a la gente le gustaba ir a “Mayo”, se sacralizó la fiesta y se empezaron a realizar unas misas de campaña en la explanada de Valdehierro, pero sin ermita ni nada, solamente con una mesa a modo de altar y los instrumentos de consagrar.

En los años 50 se pensó en construir una ermita en ese mismo lugar, con la aportación de muchos madridejenses gracias al empeño de Juan-Antonio Jiménez García-Miguel, entre otros, utilizando para ello piedras de chozos y majadas que había alrededor y barro para hacer tapial.

A la vez, se cogió una imagen que estaba perdida en la sacristía de la ermita del Cristo y se la consagró con el nombre de Virgen de Valdehierro. Es un caso extraño que una imagen se llame como una zona y no viceversa como es lo común.

Desde entonces, el 1 de Mayo se realiza una romería en su honor, donde acude la práctica totalidad de madridejenses y una cantidad cada vez mas abultada de gente de los alrededores. Hay una misa al aire libre y la explanada sirve de mercadillo y de feria con atracciones.

El domingo anterior se lleva a la Virgen en andas (18 kilómetros) y ya empieza la fiesta, porque mucha gente se va quedando en las casas que hay por el lugar, o bien, acampando en los pinares aledaños.

La devoción que ha adquirido la Virgen de Valdehierro ha sido tan grande, que en el año 1990 se la declaró por parte del Pleno del Ayuntamiento Patrona de la Villa de Madridejos y Alcaldesa Perpetua.