L'arxidiòcesi actual té els seus orígens a principis del segle xix, quan el que ara és l'oest del Canadà era un vast territori controlat per la Companyia de la Badia d'Hudson. Molts dels empleats de la companyia eren francocanadencs de fe catòlica; alguns indis i, especialment, els mestissos convertits al catolicisme. En 1838 dos sacerdots, que viatja a la Costa Oest es va aturar a Edmonton i van celebrar la primera missa, aprofitant l'oportunitat d'administrar baptismes i consagrar els matrimonis cristians.
A principis de la dècada de 1840 el bisbe de Saint-Boniface Norbert Provencher es va interessar en aquesta part de la seva vasta diòcesi. El 1843 va fundar la primera missió catòlica de l'Alberta a Lac Sainte Anne, on van trobar sojorn diversos missioners, entre ells els missioners Oblats de Maria Immaculada. Un d'ells, el pare Albert Lacombe, fundada prop d'Edmonton una missió que va prendre el nom de Sant Albert. El 1868 els superiors majors dels missioners oblats decidiren la fundació del vicariat de les missions del Canadà occidental i Vital-Justin Grandin va esdevenir el superior religiós de l'immens territori de la missió que de Saint-Boniface arribava a les costes del Pacífic i l'oceà Àrtic.
Tres anys més tard, el 22 de setembre de 1871, el Papa Pius IX va erigir la diòcesi de Sant Albert, amb territori pres de la diòcesi de Sant-Boniface. El primer bisbe va ser l'oblat Vital-Justin Grandin, i la seva congregació religiosa va quedar encarregada de la nova diòcesi.
La construcció del ferrocarril (1881-84) que connectava les regions de l'Atlàntic amb les occidentals va contribuir a l'arribada de molts immigrants, entre ells catòlics, augmentant el nombre dels fidels de la diòcesi, que fins llavors es limitava principalment a l'element indígena. A la mort de Vital-Justin Grandin el 1902 la diòcesi de St. Albert tenia prop de 18.000 fidels, 30 parròquies, amb uns quaranta sacerdots religiosos dels Oblats de Maria Immaculada i deu sacerdots seculars.
Al 1889 es va donar jurisdicció sobre el territori de Saskatchewan als bisbes de Saint-Bonifacie. El 30 de novembre de 1912 va cedir una part del seu territori per a la creació de la diòcesi de Calgary; al mateix temps la seu episcopal va ser transferida de Saint Albert a Edmonton i elevada al rang d'arxidiòcesimetropolitana amb el nom actual.
Durant l'episcopat d'Henry Joseph O'Leary es va fundar el periòdic de la diòcesi el 1921 i es va establir el seminari en1927, en els locals que abans havien servit com a institut teològic dels Oblats de Maria Immaculada. El 1957 l'arquebisbe John Hugh MacDonald va inaugurar les instal·lacions del nou seminari. Finalment, el tercer seminari va ser inaugurat el 1997.
