The Choctaw Nation signed the Treaty of Doak's Stand in 1820, ceding part of their ancestral home in the Southeastern U. S. and receiving a large tract in Indian Territory.

Most of the remainder of the Choctaw were removed to Indian Territory, escorted by federal military troops, in several waves.

[3] In 1832, the Federal Government constructed the Choctaw Agency in Indian Territory about 15 miles (24 km) west of Fort Smith, Arkansas.

In the late 1850s, it was designated as a stage stop (Walker's Station) for the Butterfield Overland Mail route.

In 1834, the U. S. Army built Fort Coffee a few miles north of Skullyville, but reassigned the garrison after four years.

The Methodist Church took over the facility, converting it for use as the Fort Coffee Academy for Boys, a missionary school.

In 1892, the Tushkalusa (black warriors) Freedmen Boarding school opened three miles southeast of Talihina.

In 1896 the Kansas City, Pittsburg and Gulf Railroad (acquired by the Kansas City Southern Railway in 1900) built tracks through the region from north to south, exiting into Arkansas near the Page community in southern LeFlore County.

In 1900-01 the Poteau Valley Railroad built a line from Shady Point to Sutter (later known as Calhoun, which they abandoned in 1926.

In 1901 the Fort Smith and Western Railroad connected Coal Creek west to McCurtain in Haskell County.

In 1903-04 the Midland Valley Railroad laid tracks from Arkansas west through Bokoshe to Muskogee.

[3] Prior to statehood, the area that became LeFlore County was part of Moshulatubbee and the Apukshunnubbee districts.

[3] Lake Wister, a flood control reservoir, is in the central part of the county, formed behind.

[5] The Ouachita National Forest, in the county's southern half, and Heavener Runestone State Park are tourist attractions.