On the eve of the American Civil War in 1861, a significant number of Indigenous peoples of the Americas had been relocated from the Southeastern United States to Indian Territory, west of the Mississippi. The inhabitants of the eastern part of the Indian Territory, the Five Civilized Tribes, were suzerain nations with established tribal governments, well established cultures, and legal systems that allowed for slavery. Before European Contact these tribes were generally matriarchial societies, with agriculture being the primary economic pursuit. The bulk of the tribes lived in towns (some covering hundreds of acres and containing thousands of people) with planned streets, residential and public areas. The people were ruled by complex hereditary chiefdoms of varying size and complexity with high levels of military organization.

By the middle of the 19th century, the United States Government had started leasing land from the Five Civilized Tribes (ex. Choctaw and Chickasaw) in the western, more arid, part of Indian Territory. These leased lands were used to resettle several Plains Indian tribes that tended to be nomadic in nature, embracing the horse culture. At the extreme, the Comanche society was based on patrilinear and patrilocal extended family sharing a common language; they did not develop the political idea of forming a nation or tribe until their relocation to Indian Territory.

At the beginning of the Civil War, the Union army was withdrawn from Indian Territory exposing the Five Civilized Tribes to aggression from the Plains Indians. The Confederacy filled the vacuum. All of the Five Civilized Tribes as well as other surrounding tribes signed treaties with the Confederacy. As a part of reconstruction, the Southern Treaty Commission was created by Congress to write new treaties with the Tribes that sided with the Confederacy.

An important consequence of the Reconstruction Treaties, signed in 1866, was the emancipation of 7,000 black slaves and the abolition of slavery.

The Choctaw Nation and Chickasaw Nation in Indian Territory strongly support the Confederacy which signed the Treaty with Choctaws and Chickasaws. The Cherokee Nation, Muscogee (Creek) Nation and Seminole Nation had troops fighting on both sides. Other tribes such as Osage, Seneca, Seneca and Shawnee of the Neosho Agency, and Quapaw Tribes also signed treaties with the Confederacy.

During the Civil War, the Union Congress passed a statute that gave the President the authority to suspend the appropriations of any tribe if the tribe is "in a state of actual hostility to the government of the United States… and, by proclamation, to declare all treaties with such tribe to be abrogated by such tribe"(25 U.S.C. Sec. 72).

The term Reconstruction Era typically covers the transformation of the Southern United States in the decade after the Civil War. However, the reconstruction of the Indian Territory lasted significantly longer and fostered policy changes that impacted other tribes in the rest of the country.

As a component of Reconstruction, a "grand council was called by the President of the United States, through the department of the Interior, to which a summons was issued to each of the five tribes to send representatives. This call was mandatory as far as it related to all Indian tribes which had been identified by treaty or otherwise with the late southern confederacy. Word was also given to other tribes, many of whom had reservations in Kansas." The Council, the Southern Treaty Commission, held in Ft. Smith, Arkansas, was attended by hundreds of Indians representing dozens of tribes. Over the next several years the commission negotiated treaties with different tribes that resulted in additional relocations to Indian Territory and the de facto creation (initially by treaty) of an unorganized Oklahoma Territory.