L'origine della Cattedrale di Aosta risale alle fasi iniziali di diffusione del Cristianesimo in Valle d'Aosta: già verso la fine del IV secolo, esisteva, dove oggi si trova la cattedrale - come provato dagli scavi archeologici- una Domus Ecclesiae di ragguardevoli proporzioni (con una navata di circa 40 metri). La chiesa venne completamente rifatta nel corso del secolo XI, probabilmente per volere di Anselmo che fu vescovo in Aosta tra il 994 e il 1025 (da non confondersi con Anselmo, filosofo e santo, nato in Aosta nel 1033). Il complesso architettonico, eretto in stile romanico di gusto nordico, doveva constare di due edifici: una chiesa parrocchiale a navata unica, dedicata a S. Giovanni Battista e la cattedrale, dedicata alla Vergine, con tre navate che terminavano nelle absidi semicircolari, tuttora visibili.

La navata centrale fu interamente affrescata verso la metà del secolo XI: di tale importante ciclo pittorico rimangono alcuni frammenti nel sottotetto. Allo stesso periodo appartiene la cripta (sotto il presbiterio).

Nei tre secoli successivi la cattedrale vide trasformazioni e abbellimenti successivi: alla fine del XII secolo risalgono le vetrate (delle quali sono rimasti frammenti conservati nel Museo del Tesoro); al XII e XIII secolo vanno datati i mosaici del coro.

Ai vescovi che ressero la diocesi di Aosta in questo periodo di notevole fioritura economica ed artistica e, in particolare alla munificenza e al gusto estetico dell'arcidiacono della Cattedrale, Giorgio di Challant ( morto nel 1509), si devono le radicali trasformazioni della cattedrale in questo periodo che la portano ad assumere un aspetto assai prossimo a quello che ora vediamo. In questo periodo venne eliminato lo "jubè" formato da tre arconi che separavano il presbiterio dal resto della chiesa; furono costruite le volte a crociera e le vetrate in stile gotico. Importanti artisti transalpini aprirono le loro botteghe in Aosta per eseguire i lavori di abbellimento della cattedrale.

Tra il 1522 ed il 1526 fu realizzata una nuova facciata, in stile rinascimentale, e si eseguì la decorazione del portico con i affreschi e stucchi.

I secoli successi videro interventi circoscritti: lavori di sistemazione ed abbellimento delle cappelle (come gli affreschi della cappella dei signori di Cly, ca. 1570-80), la realizzazione di interessanti opere di orificeria, la costruzione in marmo di un nuovo altar maggiore (1758). L'intervento più importante fu la costruzione tra il 1846 ed il 1848, ad opera dell'architetto Gayo, della nuova facciata neoclassica, posta in posizione più avanzata rispetto al portico. Di tale periodo è anche la costruzione della neogotica cappella del Rosario, di gusto discutibile, che comportò la demolizione di una parte dell'elegante chiostro costruito nella seconda metà del XV secolo.