The name Oktibbeha is a Native American word meaning either "bloody water" (because of a battle fought on the banks) or possibly "icy creek". Indian artifacts more than 2000 years old have been found near ancient earthwork mounds just east of Starkville, showing the area has been inhabited at least this long. These have been used to date the construction of the mounds to the Woodland period, ending about 1000 A.D. The Choctaw people, one of the Five Civilized Tribes of the Southeast, occupied extensive territory in this area for centuries prior to European encounter. The Indian Mound Campground nearby was named for the earthwork monuments.
Artifacts in the form of clay pot fragments and artwork dating from that period have been found east of Starkville at the Herman Mound and Village site, which is listed on the National Register of Historic Places and can be accessed from the Indian Mound Campground. Shortly before the American Revolutionary War period, the area was inhabited by the Choccuma (or Chakchiuma) tribe, who were annihilated at a settlement known as Lyon's Bluff by a rare alliance between the Choctaw and Chickasaw, who were traditional rivals. The modern early settlement of the area was started during the period of Indian Removal, after the Choctaw of Oktibbeha County ceded their claims to land to the United States in the area in the Treaty of Dancing Rabbit Creek in 1830. They were removed to other lands west of the Mississippi River, in Indian Territory, what is now the state of Oklahoma.
Like the indigenous peoples before them, white settlers were drawn to the Starkville area because of two large natural springs. The Choctaw Agency was set up near what is now Sturgis, first to deal with the Choctaw and later to organize the selling of their lands to the new inhabitants. What was originally a trading post was located on Robinson Road, about 1.5 miles east of the Noxubee River.
A lumber mill southwest of town produced clapboards, from which the settlement took its original name of Boardtown. In 1835, Boardtown was established as the county seat of Oktibbeha County, and its name was changed to Starkville in honor of Revolutionary War hero General John Stark.
In 1876, in a largely successful attempt by whites to suppress the black vote in the Reconstruction era, a group of eighteen white men known as White-Liners, led by Dorsey Outlaw, surrounded the Republican Club in the community of Chapel Hill near Choctaw Agency. They fired upon the black members from ambush, shooting them in the back. One man, Charles Curry, was killed instantly, and 36 were wounded, four of them possibly mortally wounded. Jeff Gregory died the following day. The same group of White-Liners continued to Artesia the next day to intimidate black voters in that area, and on to Columbus the next day.
The state legislature founded Mississippi State University near Starkville in 1878 as a land-grant university. It has become a major research university. Since the late 20th century, Oktibbeha, along with Clay and Lowndes counties, have been designated along with their respective counties as the Golden Triangle in Mississippi. They share a goal of collaborative economic development among the three counties and their major jurisdictions.
In 1912 Mann Hamilton, a black man, was accused of assaulting a white woman, June Bell, at Bell's school house near Maben. Although Sheriff Nickles attempted to gain custody of the accused, he was directed to the wrong location and Hamilton was lynched, hanged by a white mob. This was one of six lynchings of African Americans committed by whites in the county in the post-Reconstruction period and extending into the early 20th century.
Oktibbeha county has a total area of 462 square miles, of which 458 square miles is land and 4 square miles (0.8%) is water. The population recorded in the 1840 Federal Census was 4,276. The 2010 census recorded 47,671 residents in the county.
Neighboring counties are Noxubee County (southeast), Winston County (south), Choctaw County (west), Webster County (northwest), Clay County (north), and Lowndes County (east).
Communities in the county include Starkville, Maben, Sturgis, Adaton, Blackjack, Bradley, Clayton Village, Hickory Grove, Josey Creek, Longview, Morgantown, Oktoc, Osborn, Self Creek, Sessums, Agency, Bell's Mill, Chapel, Cedar Grove, Collier's Tanyard, Double Springs, Ebenezer, Folsom, Grab All, Hassie, Kemper, Lincecum's Mill, Muldrow Station, Prospect, Red Acre, Steelville, Trimcane, Whitefield, and Yanaby.