King Alfonso VI and Pope Gregory VII named Burgos an episcopal see in 1075, continuing the episcopal legacy of the medieval diocese of Oca, whose prelate signed the 3rd Council of Toledo in 589.

The monarch promoted the construction of a cathedral dedicated to the Virgin Mary, whose outline is unknown but is presumed to be Romanesque and similar to contemporary works (the church of Silos, the monastery of San Pedro de Arlanza, the church of San Martín de Frómista, and the cathedral of Jaca). Documents show that the monarch donated the land of his father Fernando I's royal residence and a little chapel dedicated to Santa María, which was under construction, for the enormous effort.

This cathedral was built in 1096, but it was too tiny for a city that was the symbolic capital of the realm, a powerful episcopal see (the cathedral chapter had more than thirty members before 1200), and a growing commercial center. At the start of the 13th century, a new cathedral was decided upon. As was typical at the time, the Romanesque building (of which only a few sculptural elements remain) was destroyed and the new Gothic cathedral was built on its site, augmented by demolishing some surrounding homes provided by Bishop Marino.