The Mississippian culture of Caddoan-speaking Mound Builders (around A.D. 850 to 1450), which included the Spiro Mounds Site, also reached into Pittsburg County. There has been little evidence of Paleo-Indian (prior to 6000 B.C.) occupation, with those few excavated sites usually the location of a large mammal kill. Archaic Period (6000 B.C. to A.D. 1) sites, especially those of the Late Archaic, show an increased use of local resources, and the occupations were mainly open camps. Archaeologists have surmised that the Jack Fork Basin, which encompasses southeastern Pittsburg County, had its most intense prehistoric usage during the Late Archaic through the Early Caddoan time frame. The Canadian River was explored and traversed by Europeans and Americans as early as 1719 by Jean Baptiste Bénard de La Harpe. Other traders and explorers in the region have included brothers Pierre and Paul Mallet, Stephen H. Long, and Randolph B. Marcy.

In 1830 the Treaty of Dancing Rabbit Creek ceded the Choctaws' remaining land in the southeastern United States and precipitated their final removal into Indian Territory, including present Pittsburg County. The Texas Road and one route of the California Road cut through the area, creating Choctaw settlements that benefited from travelers. One of these, Perryville, was near both trails. Established by James Perry circa 1840, the village at various times had post offices, blacksmiths, a hotel, a stage stand, and Colbert's Institute, a school for Chickasaw children. When the railroad bypassed the community in 1872, its businesses and residents moved, many to nearby McAlester.

The present county served as a transportation corridor in the mid-nineteenth century. From 1858-61 the Butterfield Overland Mail route crossed this portion of the Choctaw Nation, as did subsequent stage companies following the course. Blackburn's Station, nine miles southeast of the present town of Pittsburg, served as a stage stop. Blackburn's Station Site was added to the National Register of Historic Places in 1973.

During the Civil War Perryville served as Confederate post and supply depot. In 1863 Union forces under Maj. Gen James Blunt burned the town after the Battle of Perryville. In 1972 the Perryville site was added to the National Register of Historic Places. The only other county Civil War site was Confederate Camp Jumper, named for Seminole Chief John Jumper and located approximately five miles north of McAlester.

After the Civil War James J. McAlester, already familiar with the coal deposits in the Perryville vicinity of the Choctaw Nation, moved to the region and eventually owned his own trading post. In 1872 he married a Chickasaw, obtaining citizenship rights in the Choctaw and Chickasaw nations. These rights and the construction of the Missouri, Kansas and Texas Railway (MK&T) in 1872 from north to south in the vicinity led him to claim the coal deposits. With partners, McAlester leased the coal lands to the Osage Coal and Mining Company. Soon, the town of McAlester developed, serving the area's coal industry. Other towns hosted mining interests, including Adamson, Alderson, Dow, Haileyville, Hartshorne, Krebs, Quinton, and Savanna. In the late nineteenth century the companies imported foreign miners, at first workers from the British Isles, then other European countries, and finally African American and Mexican miners.

The coal industry attracted more railroads, with many owning the mining interests served by their tracks. In 1872 the Osage Coal and Mining Company (owned by the Missouri Pacific Railway and acquired by the MK&T in 1888) built spurs from the MK&T tracks at North McAlester to Krebs Junction and from there to Krebs proper. In 1889-90 the Choctaw Coal and Railway (CC&R) laid tracks from Wister to McAlester, and in 1895 the Choctaw, Oklahoma and Gulf Railroad (CO&G), which had acquired the CC&R, built a line from McAlester to Oklahoma City. In 1896-99 the Missouri, Kansas and Texas Railroad constructed tracks from Krebs Junction to Mile Post Seven near Wilburton. In 1902 the Western Oklahoma Railroad, obtained by the CO&G later that year, built a line from Branch Junction, near Haileyville to Ardmore. In 1902 the CO&G also relocated part of its trackage between Wilburton and Haileyville, and the Fort Smith and Western Railroad built a line from McCurtain to the South Canadian River in a northwesterly direction through present Pittsburg County. In 1903-04 the Choctaw Railway and Lighting Company took advantage of some of the coal town's proximity by building an street railway system and interurban line between McAlester and Hartshorne. In 1916 the company was reorganized as the Pittsburg County Railway Company, later a subsidiary of the Public Service Company of Oklahoma.

In 1887 a report for the Commissioner to Indian Affairs estimated the Choctaw Nation coal production at 600,000 tons, with many of the mines in present Pittsburg County. The 1908-09 Chief Mine Inspector of Oklahoma's report for District Number Two, which consisted solely of Pittsburg mines, showed 731,298 tons produced. After 1920 production slowed, and by 1940 Pittsburg, Haskell, and Sequoyah counties combined produced only 256,507 tons. A brief upswing occurred during World War II, but by 1964 Pittsburg County extracted 448 tons, all strip mined. In 1966 the annual mine report on coal did not mention the county.

The early coal mines had a national reputation as some of the most dangerous, and several mine disasters transpired. In 1892 the Osage Coal and Mining Company suffered one of the deadliest accidents when reportedly one hundred miners died and another two hundred were injured. The other Pittsburg coal communities also suffered tragedies. Haileyville lost twenty-nine miners in a 1908 accident, McAlester sixty-one in a 1929 disaster and thirty in another the next year, and twelve Savanna miners died trying to recover six of their fallen comrades in 1887. Hundreds of others lost their lives during the mining era. They are memorialized at McAlester's Chadick Park, and the Mass Grave of Mexican Miners in Mount Calvary Cemetery is listed in the National Register of Historic Places.

Agriculture has been an economic staple, enduring after the coal industry declined. In 1908 corn (39,875 acres planted) and cotton (21,897 acres) served as the two largest cash crops, with barley a distant third (638 acres), and little wheat (80 acres) planted. That year farmers controlled 20 percent of the county's total land. By 1935 the county supported 4,291 farms, with 53,648 acres of corn and 40,976 acres of cotton planted in 1934. In 1960 cotton had been reduced to 3,250 acres and corn to 5,100 acres. Sorghum was planted on 12,300 acres, oats on 2,800, and wheat on 1,000. In 1960 farms and ranches numbered 1,556, and by 1997, 1,586. In 2000 wheat outnumbered other crops, with 3,000 acres planted. In 1908 Pittsburg County ranchers prospered with 33,679 head of cattle, 4,470 horses, and 16,462 swine. By 1930 the number of cattle decreased to 15,336, with 4,999 horses and 3,918 swine. Cattle raising increased as the coal industry continued to decline, and the county reported 60,000 head in 1960. In 2000 county ranchers grazed 90,000 head. Natural gas and timber also contribute to the economy.

Several educational, charitable, and state-government institutions have been placed in Pittsburg County. In 1891 near present Hartshorne the Choctaw Nation established Jones Academy, a boarding school for boys that continued into the twenty-first century with a new mission to serve American Indian students from mostly low-income, single-parent homes. The children attend the Hartshorne public school, but secure counseling and other activities at Jones. A statewide campaign for a state prison brought that aspect of government to the area. In 1911 construction of the Oklahoma State Prison began at McAlester, and the facility opened in 1914 with more than six hundred inmates. In 1973 the institution gained infamy when one of the nation's worst prison riots occurred, lasting more than a week and causing $20 million in damage. The penitentiary annually hosts a prison rodeo on the weekend before Labor Day.

The military-industrial complex of the World War II era found McAlester's location ideal. In 1942 the U.S. Navy designated the area for the location of an ammunition depot. The plant opened in 1943, and the workforce peaked at eight thousand in 1945. In 1977 the U.S. Army took control of the depot, and at the end of the twentieth century it continued to employ more than eight hundred workers. Also, the creation of Lake Eufaula brought economic prosperity to Pittsburg County. From 1956 to 1964 the U.S. Corps of Engineers constructed Lake Eufaula dam, creating Oklahoma's largest lake (102,200 acres). A boon to northern Pittsburg County, Lake Eufaula brought tourism, land development, and implementation of hydroelectric power to the area.

Transportation access and medical resources allowed McAlester to become the center of the region. In 1966 the official dedication of the portion of the Indian Nations Turnpike that connected McAlester to Henryetta, and the second section, connecting the first to Hugo, opened in 1970. The tollway crossed Pittsburg County from north to south. Other arteries included U.S. Highways 69 and 270 and State Highways 1, 2, 9, 31, 63, 71, and 113. McAlester also has attracted numerous manufacturing and health facilities, including All Saints Hospital, one of the first in Indian Territory. At the beginning of the twentieth century the city housed McAlester's Regional Health and Cancer Center and a branch of Eastern Oklahoma State College.

The county's population at its 1907 creation stood at 37,677, and it increased to 47,650 by 1910 and peaked at 52,570 in 1920. With the demise of the coal industry and the onset of the Great Depression, by 1940 the population had fallen to 48,985. With the post-World War II rural-to-urban shift the decline continued, reaching 41,031 in 1950 and 34,360 in 1960. The trend reversed, with the 1970 census reporting 37,521 residents and the 1980 census, 40,524. In 2000 Pittsburg County's population stood at 43,953. 77.5 percent were white, 11.9 percent American Indian, 3.8 African American, 2.6 Hispanic, and 0.5 Asian.

Pittsburg County has produced several influential state and national politicians, including Carl Albert (Speaker of the U.S. House of Representatives), Wilburn Cartwright, George Nigh, Gene Stipe, Kirksey Nix, and C. Plowboy Edwards. At the beginning of the twenty-first century the county had twenty-five properties listed in the National Register of Historic Places. These included the St. Joseph's Catholic Church and Hokey's Drugstore in Krebs, a town known for its historically large Italian population. McAlester had fifteen properties, including the Aldridge Hotel, the Federal Building and U.S. Courthouse, the McAlester National Guard Armory, the McAlester Scottish Rite Temple, and the Pittsburg County Courthouse. Hartshorne's Sts. Cyril and Methodius Russian Orthodox Greek Catholic Church originally served the area's Carpatho-Russian parishioners, and its three "onion" domes make it a local landmark.