The 1875 North-West Territories Act stipulated that the Lieutenant-Governor of the North-West Territories must reside in the region, thereby necessitating the establishment of a territorial capital. Prince Albert was the only sizeable settlement in the region in 1875, but, in what has been called one of the great mysteries of western Canadian history, Fort Livingstone was named the first territorial seat of government. Located near present-day Pelly, and populated by more snakes than people, the fort served as the headquarters of the North-West Mounted Police when David Laird was appointed Lieutenant- Governor in November 1876. The first session of the North-West Council was subsequently held there the following March.
The NWMP headquarters moved when Laird left Fort Livingstone in August 1877 to establish a new capital at the more centrally located Telegraph Flat, later renamed Battleford. Government House, which stood until it was destroyed by fire in 2003, was erected to serve the purposes of the Lieutenant-Governor and his staff. The settlement's prestige was bolstered by a visit from the Governor General of Canada (and son-in-law of Queen Victoria), the Marquis of Lorne, in the fall of 1881. A permanent capital, authenticated by official buildings and royal visits, and an administrative body helped reinforce the Canadian government's rather precarious authority over the North-West.
Edgar Dewdney succeeded Laird in December 1881. Battleford had originally been selected with the belief that the Canadian Pacific Railway would pass through the town, but by 1881 the railway route been had altered to a more southern path. Dewdney, in consultation with Prime Minister John A. Macdonald and W.C. Van Horne, the general manager of the Canadian Pacific Railway, decided in June 1882 to move the territorial capital to Regina, effective March 1883. The fact that Dewdney himself owned land in Regina was likely a factor in the process. In 1905, Regina, as the territorial capital, was the logical choice for the location of the new provincial capital as well.