La capitale provinciale de la Saskatchewan n'a pas toujours été telle qu'elle est aujourd'hui. Son histoire commence très modestement. Le lieu est visité par des Autochtones qui font la chasse au bison. Cet endroit est alors connu comme « Oskana » ou « Wascana », nom du ruisseau qui alimente aujourd'hui le lac Wascana près du palais législatif. Il porte aussi le nom de « Oskana Kasasteki », « Oskunah-Kasa-Take ». Du côté anglais, les noms sont marqués par la présence de très nombreux os de bison : « Pile O'Bones », « Bone creek », « Manybones ». Il en est de même en français, avec le nom « Tas d'os ».
C'est à partir de 1881 que le lieu prendra son importance. Le chemin de fer alors en construction annonce sa trajectoire au sud de la province et on doit choisir une nouvelle capitale pour les Territoires du Nord-Ouest. Parmi les lieux prisés, il y a Moose Jaw et Fort Qu'appelle. Finalement, c'est le lieutenant gouverneur, l'honorable Edgar Dewdney, qui tranchera la question. En effet, avec des collaborateurs, il a acheté 28 sections de terre de la Compagnie de la Baie d'Hudson et la nouvelle capitale pourra lui permettre de revendre ces terres à gros prix. En 1882, la capitale passe donc de Telegraph Flat (ou Plaine du télégraphe, aujourd'hui Battleford), aux rives du ruisseau Wascana. Par contre, les noms qui existaient jusqu'à présent pour désigner les lieux ne sont pas jugés assez honorables. La princesse Louise, fille de la reine Victoria, conseille son mari le marquis de Lorne, alors Gouverneur général du Canada, dans le choix d'un nouveau nom pour la capitale. Il choisit Regina, mot latin pour reine, afin d'honorer sa belle-mère. Malgré cette décision, le Canadien Pacifique construira sa gare à deux milles de la capitale.
Parmi les premiers habitants de la nouvelle capitale, il y a Pascal Bonneau, son épouse et sa famille de 10 enfants. D'abord dans la région pour travailler à la construction du chemin de fer, il voit la nouvelle capitale comme une opportunité de commerce et il ouvre un magasin général.
En 1882, c'est au tour d'Henri Lejeune d'arriver à Regina pour ouvrir la banque Lafferty and Smith. La police à cheval du Nord-Ouest (PCN-O) installe son quartier général à Regina en 1883. Quelques années plus tard, en 1891, le lieutenant-gouverneur, Joseph Royal, un canadien-français, emménage dans sa nouvelle résidence, aujourd'hui « Government House ». La capitale compte alors 1200 habitants. Le bâtiment devient alors le centre socioculturel.
La première église bâtie à Regina est une église méthodiste, construite en 10 jours en 1882. Elle sert à la fois de tribunal, de secrétariat municipal et de « public lecture Hall ». Vient ensuite l'église anglicane de Saint-Paul, consacrée en juin 1884, suivie en août de la même année, de l'église catholique de Ste-Marie, qui possédait la première cloche de Regina, lourde de 300 livres. L'année suivante, les presbytériens construisent l'église Knox.
Les débuts sont difficiles. Même si l'année 1891 est une année record pour les récoltes, les années 1884, 1886, 1892 et surtout 1894 sont médiocre. Durant la dernière année, la ville est victime d'une épidémie de fièvre typhoïde. L'installation d'un système d'égouts aide grandement à calmer la crise. Durant cette période, la ville se dote également d'électricité (1890) et d'un système de tramways électrique. Malgré toutes ces difficultés, la population augmente rapidement. De 1889 à 1891, la population passe de 997 habitants à 1681. On note une forte immigration allemande catholique.
Les années suivantes sont cependant notées par le racisme anglo-saxon. À Regina par exemple, on s'oppose à l'installation de nouveaux immigrants juifs russes. Même les franco-canadiens ne sont pas les bienvenus. Cela est particulièrement notoire lorsque Frederick Haultain met en place une mesure pour réduire l'enseignement en langue française ainsi que l'enseignement catholique. La même année, Haultain retire également le français de la législature des Territoires du Nord-Ouest. Malgré tout, la population ne cesse d'augmenter et atteint les 3000 habitants en 1903.
Finalement, en 1905, Regina devient la capitale provinciale, quelques temps après la création de la Saskatchewan
