The church began as a large Pre-Romanesque basilica in the present location of the Gothic cathedral, but nothing more is known about that first building, built by order of King Alfonso II of Asturias.

The origins of Oviedo Cathedral date back to the late 8th century, when Asturian king Alfonso II of Asturias promoted the construction of a basilica at the core of the Kingdom of Asturias' newly established royal court (regia sedes): what today conforms the oldest part of Oviedo's historic centre was then a political and religious complex that included a royal palace, several churches, monasteries, baths, stables, etc.

The building known as Cámara Santa ("Holy Chamber") is the most important surviving structure from the primitive pre-Romanesque royal complex: it is a two-story building with a rectangular plan, which shelters several burials in its lower floor and keeps a collection of royal treasures and relics in the upper floor, like the well-known Cross of the Angels ("Cruz de los ángeles") and the Victory Cross ("Cruz de la victoria"), both of them important symbols of the Asturian monarchy.

During the 12th century, because of the constant flow of pilgrims and visitors, the Cámara Santa was reformed: it was then when the aisle in the upper floor was decorated with an excellent group of late Romanesque column statues depicting the Apostles; additionally, a barrel vault was added, replacing the former ceiling made of wooden beams.

During the Late Middle Ages, Oviedo Cathedral underwent major changes, becoming the most important architectural workshop of Asturias: between c. 1300–1550, the old pre-Romanesque basilica, as well as its presumed Romanesque premises, were demolished and replaced by a set of classic and flamboyant Gothic elements, including the chapter room, the cloister, the main chapel and the aisles, as well as the western facade and tower.

The chapter room was probably built between 1293 and 1314: it is the cathedral's oldest Gothic structure, a diaphanous, square-plan hall covered by an eight-sided dome, under which several noble lineages decided to build their burials.

The Gothic cloister was already a work in progress around 1300, although it wasn't finished until the mid-15th century: it was built thanks to the generous contributions of the Camara Santa's Brotherhood (established in 1344), several noble patrons and Castilian king Alfonso XI, as well as the money gathered by the bishop's tax collectors.

By 1500, the cathedral was almost finished, with exception of its western facade: that very year, master builder Juan de Badajoz "el Viejo" ("the Elder") became the new director of the episcopal workshop, starting the construction of a prominent narthex which would form a spacious passage, working as a covered street: it must be reminded that the original surroundings of Oviedo Cathedral were cluttered with houses, and the walkable areas were very narrow, so this street-like narthex provided an interesting, urbanistic solution.

In the 18th century, the adjacent church of Santa María del Rey Casto—an old, pre-Romanesque basilica built by king Alfonso II as a funerary pantheon for the Asturian monarchy—was torn down and replaced by a new, late Baroque chapel with exuberant decoration.

Bishop Pelagius relates that the Agate Box, a coffer made by the disciples of the Apostles and containing the most precious relics of the Holy City, was taken from Jerusalem to Africa, and after residing in several locations was finally placed at Oviedo by Alfonso II.