The base on which the church is built is one of the largest pyramids of the ancient world, being 54 metres (177 ft) high, covering 54 acres and shaped by several superimposed structures over the course of six centuries.

Legend tells that one of Cortés's soldiers, Gonzalo Rodriguez de Villafuerte, had with him one of the little religious images known as castrenses, and he hid it among the aloe plants in order to carry out a devotional action of thankfulness.

The legend tells that during the battle, a young girl threw dirt in the eyes of the attacking natives helping to seal the Spanish victory.

It was in Veracruz where Rodríguez de Villafuerte presided at the first mass celebrated in Mexico, on April 21, 1519, the same year as Hernán Cortés's mandate was affirmed by the Spanish in the Templo Mayor of Tenochtitlan.

[4] In 1520, when the Spanish under Cortés were defeated by the Aztecs while fleeing by way of Naucalpan, de Villafuerte concealed the image in a native temple on the highest part of the hill of Otocampulco.

Twenty years later, indigenous people discovered it there under an aloe plant, and from then on, the virgin was kept in the house of the chief of San Juan Totoltepec, until he built a chapel.