The area that became Wagoner County, Oklahoma was home to members of the Muscogee (Creek) and Cherokee nations, who had been removed by force during the Trail of Tears from their original homelands in the southeastern United States and relocated to Oklahoma.
As railways spread west, the town of Wagoner sprang up, located at the intersection of the Kansas and Arkansas Valley Railway and the Missouri, Kansas, and Texas (MK&T) Railway. In 1887, MK&T firefighter William McAnally opened a hotel at the intersection of the two lines, located within Indian Territory; additional hotels and general stores followed. Cattle shipping emerged as a major Wagoner industry. During the 1890s, Wagoner's population multiplied, growing from 642 recorded residents in 1894 to around 1500 in 1896. This growth occurred in part thanks to the town newspaper's initiative in printing positive reviews of the town and recruiting new settlers to share its prosperity.
In 1896, Wagoner became the first incorporated town in Indian Territory. A city government was established, along with a courthouse, schools, law enforcement, and utilities. Changes in real estate and property management also contributed to the fast growing settler population. As a consequence of the Dawes Commission, Indian Territory land was transferred from tribal title to individual ownership, which paved the way for some of this land to be sold to settlers.
Oklahoma became a state in 1907; by then, Wagoner's population had reached 2950. It was designated the seat of Wagoner County due in part to its size and courthouse.