The Georgia Militia originally constructed Fort Mitchell in order to sustain a military presence in the area during the Creek War of 1813 to 1814.

In 1818, a post office was added to the newly extended Federal Road that crossed through Fort Mitchell from Augusta, Georgia, and westward into the Alabama Territory.

In response to Native American protests, a new fort was constructed and occupied by the 4th U.S. Infantry in summer 1825, and it remained garrisoned almost continually through 1840.

In 1831, a group of white settlers invaded the Indian community of Ola Ufalal (now Eufaula), evicted the Creeks, burned their houses, and built their own settlement.

The U.S. marshal protested the settlers' actions, and when defied, the commandant at Fort Mitchell dispatched a company to demand the surrender and evacuation of the town.

President Andrew Jackson was committed to a policy of removing Native Americans, however, and was not eager to use force against settlers who were supported by the laws of Georgia and Alabama.

For every ejection of a trespasser evacuated by troops at Fort Mitchell, 10 intruders would cross the river and enter Creek territory.