County leaders believed that its coal production compared favorably with Pittsburgh, Pennsylvania at the time of statehood.

The area forming Pittsburg County was part of the Choctaw Nation after the Choctaw tribe was forced to relocate to Indian Territory from its home in the Southeastern United States in the early 1830s.

Unlike the State of Oklahoma, whose county boundaries follow the precise north–south, east–west grid provided by Oklahoma's township and range system, the Choctaw Nation established its internal divisions using easily recognizable landmarks, such as mountains and rivers, as borders.

In 1840, James Perry established a village called Perryville that became an important stop near the place where the two trails crossed.

During the Civil War, Perryville served as an important supply depot for Confederate forces until the Union Army captured and burned the town.

It became defunct after the Missouri, Kansas and Texas Railway (MK&T) bypassed it in 1872, and the remaining inhabitants moved to McAlester.

[3] James J. McAlester moved to the Choctaw Nation in 1872, opened a trading post and married a Chickasaw woman.

When the MK&T built its line, McAlester laid claim to the coal deposits in the Perryville area, which he and some partners leased to the Osage Coal and Mining Company, which was owned by the Missouri Pacific Railroad and acquired by the MK&T in 1888.

[3] Manufacturing became significant when the U.S. Navy built an ammunition depot at McAlester during World War II.

[3] The Corps of Engineers built Eufaula Lake between 1956 and 1964, which brought tourism, land development and a major source of hydroelectric power.

Elementary only: There is a Bureau of Indian Education (BIE)-affiliated school and boarding facility, Jones Academy (education for grades 1–6, boarding only for grades 7–12) The following sites in Pittsburg County are listed on the National Register of Historic Places: