Choctaw origin legends describe a migration of the Choctaw and Chickasaw from farther west, but there is no known archaeological evidence for this. Native groups bordering the Choctaw territory at the time of European contact included the Creek east of the Tombigbee River, the Chickasaw in northern Mississippi, and the Natchez to the west on the Mississippi River. Along the Gulf Coast were closely related Choctaw-speaking tribes: the Pascagoula, the Acolapissa, and the Bayogoula. Choctaw relations with other major tribes were characterized by customary warfare associated with the receiving of young males into adulthood.
The first written account of the Choctaw is in the chronicles of the Hernando de Soto expedition in 1540. Permanent European contact began with French settlements on the Gulf Coast in 1699. The Choctaw were rapidly plunged into a complicated colonial rivalry as European powers sought to utilize Indian allies to carry out their territorial designs and to profit from the trade in guns, deerskins, and slaves. The Choctaw allied with the French operating from New Orleans in efforts to get European goods as well as guns to protect themselves from the English and their allies. With the ending of colonial rivalry and the establishment of the American nation, warfare was curtailed.
The Choctaw joined with the United States in the War of 1812 against their traditional enemies, the Creeks, and the British. But the Treaty of Fort Adams in 1801 had begun a pattern of progressive loss of Choctaw land, which resulted in removal thirty years later. In each treaty, the Choctaw were forced to cede more land and more prerogatives to the United States. Choctaw leaders such as Pushmataha were aware of the threat imposed by the growing number of White settlers in the Southeast and consciously decided to adopt White ways as a means of survival. Missionaries established schools in response to a Choctaw request. With the spread of literacy, the Choctaw adopted formal written rules passed in district councils in the place of customary law. But these changes did not affect the demand for Indian removal that resulted in the Treaty of Dancing Rabbit Creek in 1831 requiring the removal of the Choctaw to Oklahoma.
Under this treaty, Choctaws could elect to remain in Mississippi with individually owned lands, but when large numbers attempted to use this provision, the treaty agent deliberately failed to record their claims. In the coming years, the remaining Choctaw were robbed of their possessions, and most eventually were forced to go to Oklahoma. Some Choctaw remained as subsistence farmers on unoccupied marginal lands in east central Mississippi. The descendants of these two groups compose the current Oklahoma and Mississippi Choctaw populations.