The Creek first arrived in the area in the late 1820s, and the Choctaw came in 1831-32. The northern portion of future Hughes County was located in the Wewoka District of the Creek Nation, and the southern portion of the county was situated within the Moshulatubbee District of the Choctaw Nation. One of the first settlements was Edwards's (Edwards's Store), owned by James Edwards. Built on the Little River, the post was southeast of present Holdenville. In 1834 Camp Holmes, named in honor of Lt. Theophilus Hunter Holmes, was established nearby and was a cantonment used by the 1834 Dodge-Leavenworth Expedition. Edwards's settlement moved north when the Choctaw, Oklahoma and Gulf Railroad built a line through the area in 1895. The town was named for railroad official James Franklin Holden. Because the name was so similar to another post office at Holder, the name was changed to Holdenville, and the post office opened on November 15, 1895. As the county seat Holdenville was incorporated in 1898. In 1908 voters selected Holdenville over Wetumka as the county seat. County officials used the federal building until a new courthouse was built in 1920. The edifice was designed by the Oklahoma City architectural partners Layton, Wemyss Smith, and Forsyth.

The arrival of rail transportation was paramount for Hughes County's economic development as an agricultural area. At the turn of the twentieth century four railways provided access to markets and products, the St. Louis and San Francisco Railway passed through the northwestern corner of the county, the Ft. Smith and Western Railroad through the northeastern corner, the Missouri, Oklahoma and Gulf Railway (later the Kansas, Oklahoma and Gulf Railway) northeast-southwest through the center, and the Chicago, Rock Island and Pacific Railway east-west through the center. By the 1920s approximately 85 percent of the county was used for farming, with 15 percent in timber. Cotton, corn, sorghum, and wheat were the main crops. The petroleum industry came to play a significant economic role as well, as Hughes County lay on the eastern edge of the Greater Seminole Oil Field. The field developed in the mid-1920s, and Hughes County and Holdenville participated in the boom. Refineries and other related industries clustered around Holdenville through the 1930s.

Prominent politicians have included Frank Crane, E. C. Holloway, Bob Howell, Tom Phillips, James W. Rogers, Jr., Hugh Sandlin, and Frank L. Warren. Crane was the Democratic alternate delegate to the Democratic National Convention in 1948; Holloway was Republican alternate to the national convention in 1944; and Warren was at the Republican National Convention in 1932. Among its distinguished natives is T. Boone Pickens, born in Holdenville in 1928 and founder of Mesa Petroleum Corporation; Holdenville's Grace M. Pickens Public Library is named for his mother.

Holdenville's population jumped dramatically from 2,932 in 1920 to 7,268 in 1930 due to the oil boom. In 1930 the county population peaked at 30,334, declined as the oil industry stabilized, and reached 13,228 in 1970. During the 1930s the Works Progress Administration funded the construction of several buildings that have been listed in the National Register of Historic Places, including the Holdenville National Armory (NR 88001386) and the Wetumka National Guard Armory (NR 88001390). At the turn of the twenty-first century the county population was 14,154, of which 72.8 percent were white, 16.2 percent American Indian, 4.5 percent were African American, 2.5 percent Hispanic, and 0.2 percent Asian. The county was served by U.S. Highway 75, traversing the county in a north/south direction and U.S. Highway 270, crossing the county in a east/west direction. State Highway 9 passes through the extreme northern part of the county, and State Highway 48 provides access to Interstate 40.

At the end of the twentieth century primary employers in Hughes County included Davis Correctional Center, Tyson Foods, Wes Watkins Technology Center, and Aquafarms. Retail and wholesale services as well as farming and cattle raising have also benefitted the county's economy. Primary crops have continued to include cotton, wheat, corn, oats, peanuts, and soybeans.

Local annual events are Hog Wild Days and IRA Rodeo in Holdenville and Sucker Days in Wetumka. The latter started in August 1950 after a traveling salesman sold promotional tickets for a circus that never came to town. Holdenville and Wetumka lakes also provide recreation. In August 1979 the Hughes County Historical Museum opened in Holdenville