In 1824, increasing tensions between the Cherokee and Osage Nations led the U.S. Army to relocate its westernmost presence from Fort Smith, Arkansas to a point farther west in the Arkansas territory. Colonel William Arbuckle selected a spot on the Grand River, three miles upstream from the convergence of the Arkansas, grand and Verdigris Rivers.

Colonel Arbuckle oversaw the construction of a wooden stockade named Cantonment Gibson in honor of General George Gibson. The stability of the stockade encouraged both Euro and Native Americans to settle near the post giving rise to the community at Fort Gibson, the oldest in the state of Oklahoma.

The Seventh Infantry arrived at the post in 1831, and in 1832, Cantonment Gibson was renamed Fort Gibson. Soldiers at the fort were instrumental in overseeing the resettlement of the eastern tribes to Indian Territory. For many, Fort Gibson was the last stop of the trail of Tears.

In 1857, The Army withdrew from Fort Gibson and transferred the land and the buildings to the Cherokee Nation. During the Civil war the Confederate Soldiers briefly occupied the site before establishing Fort Davis nearby. Fort Gibson was reactivated in 1863 and occupied by federal troops as a key point in controlling Indian Territory and the Texas Road. The Army served at the fort until 1871 when most troops were reassigned and the fort designated a commisary supply post. In 1872, following the arrival of the railroad to Indian Territory, the fort was reactivated to ensure law and order. In 1890, the Army abandoned Fort Gibson permanently.