The 1836 Treaty of New Echota forced the Cherokee to surrender all lands east of the Mississippi in exchange for a 7-million-acre reservation in Indian Territory and 'a perpetual outlet west...as far west as the sovereignty of the United States' extended. That western strip became the Cherokee Outlet. Two years later, the Trail of Tears brought most of the Cherokee, primarily from northern Georgia, to their new lands. A census in 1835 had counted 16,500 Cherokee. The treaty promised these lands would 'in no future time be included within the territorial limits or jurisdiction of any State or Territory.' That promise would not survive the century.

In 1865, mixed-blood Cherokee Jesse Chisholm blazed the trail that bears his name from Texas to Kansas, and the following year the first large cattle herd was driven through the Cherokee Outlet to the railroad at Abilene. For two decades, Texas longhorns streamed north along the Chisholm Trail, passing through what is now Enid. The Cherokee collected ten cents per head, though enforcement was difficult. By 1880, Kansas cattlemen formed the Cherokee Strip Livestock Association to impose order on the chaotic open range. The Cherokee eventually negotiated a five-year lease at $100,000 per year, later doubled to $200,000. More than 100 ranchers divided up the land, erecting fences, corrals, and ranch houses across a territory larger than some states.

After the Civil War, Reconstruction treaties punished the Cherokee for Confederate sympathies, requiring them to sell outlet land to displaced Kansas tribes. The Osage moved in by 1872, followed by the Kaw, Nez Perce, Pawnee, Ponca, and Tonkawa. These settlements effectively cut the Cherokee off from the western portion of their outlet, making it, in the government's own assessment, 'virtually useless' to them. Congress nullified the cattle lease in 1890 and authorized purchasing the land at $1.25 per acre. The Cherokee protested the price as far too low, having already rejected a cattlemen's offer of $3.00 per acre. President Benjamin Harrison banned all grazing after October 1890, eliminating any remaining profit. Final settlement did not come until 1964, when the Cherokee received approximately $14.7 million plus $2 million in interest.

After years of pressure, the Cherokee agreed in 1893 to cede the outlet for $8,595,736.12. That September, the eastern end was opened in the Cherokee Strip land run, the largest such event in United States history, and possibly the largest of its kind ever. The cities of Enid, Ponca City, Perry, and Woodward were all founded in the aftermath. Fourteen years later, on November 16, 1907, Oklahoma became the 46th state, absorbing what remained of Indian Territory. The land run entered American mythology, inspiring films like the 1925 Tumbleweeds starring William S. Hart and the 1939 Oklahoma Kid with James Cagney and Humphrey Bogart. But for the Cherokee, the outlet's history is a lesson in how 'perpetual' can mean barely sixty years.