Antecedentes misioneros
La evangelización católica de la región comenzó antes de la creación de la diócesis. El valle de Qu’Appelle constituyó uno de los primeros núcleos estables de presencia católica. Fort Qu’Appelle fue durante un tiempo el único asentamiento de importancia en la zona, hasta que el sacerdote Jean-Napoléon Ritchot estableció en 1865 una misión en el lugar que posteriormente recibiría el nombre de Lebret. Alrededor de estas misiones surgieron otras estaciones destinadas a la atención pastoral de las comunidades indígenas.
Los Misioneros Oblatos de María Inmaculada desempeñaron un papel central en esta primera etapa. También colaboraron otras congregaciones religiosas, entre ellas los redentoristas, los misioneros de La Salette, los misioneros de Issoudun y los Hijos de María Inmaculada. La expansión ferroviaria y la política de inmigración del Gobierno canadiense favorecieron después el crecimiento de nuevos núcleos urbanos y agrícolas. Regina, Moose Jaw, Swift Current y Yorkton se convirtieron en centros destacados de población católica.
La inmigración aportó comunidades de diversas procedencias. En los primeros años convivían católicos francófonos, germanófonos, anglófonos, polacos, húngaros y gallegos o ucranianos vinculados en parte a la tradición rutena. Esta diversidad exigió una pastoral capaz de atender varias lenguas, culturas y formas litúrgicas.
Creación de la diócesis
La Diócesis de Regina fue erigida el 4 de marzo de 1910. Su territorio comprendía la parte meridional de Saskatchewan, aproximadamente hasta el paralelo 51°30′ de latitud norte. En sus primeros años, la diócesis reunía decenas de miles de fieles y contaba con sacerdotes seculares y religiosos dedicados a las parroquias, las misiones, la educación y la atención sanitaria.
El primer obispo fue Oliver Elzéar Mathieu, antiguo rector de la Universidad Laval de Quebec, nombrado para Regina en 1911. Durante esta etapa, la diócesis desarrolló escuelas parroquiales, academias, hospitales y centros de formación profesional. La vida católica se articuló alrededor de parroquias urbanas, colonias agrícolas y misiones rurales.
Elevación a archidiócesis
El 4 de diciembre de 1915, el papa Benedicto XV erigió la provincia eclesiástica de Regina y elevó la diócesis a la dignidad de archidiócesis metropolitana. La nueva provincia quedó formada inicialmente por Regina y Prince Albert, separadas de la provincia eclesiástica de San Bonifacio. Oliver Mathieu fue nombrado primer arzobispo de Regina.,
La creación de la provincia respondía a la extensión territorial de Saskatchewan, al crecimiento de su población católica y a las dificultades de comunicación propias de una región amplia y en rápida transformación. La Santa Sede consideró conveniente dotar a la provincia civil de una estructura eclesiástica propia y estable.
Modificación territorial de 1930
En 1930, la Santa Sede separó de la Archidiócesis de Regina un extenso territorio meridional para erigir la Diócesis de Gravelbourg. La nueva diócesis comprendía la zona situada junto a la frontera con Alberta y los Estados Unidos, lo que redujo considerablemente la extensión de la archidiócesis metropolitana.
Esta reorganización permitió adaptar la administración eclesiástica al crecimiento demográfico y a la aparición de nuevos centros parroquiales en el sur de Saskatchewan.