In 1804 Gaines was appointed to work for the federal government as an assistant Indian factor at the Choctaw Trading House in St. Stephens, Mississippi Territory (now in Alabama).

As tensions grew as settlers encroached on Choctaw land and competed for natural resources, Gaines was able to maintain a degree of calm in the region.

After the Fort Mims massacre in 1813 by a faction of the Creek Indians, Gaines convinced the Choctaw and Chickasaw to help defend the lower Tombigbee River valley.

Gaines resigned his position at the Choctaw Trading House in 1818 to join the Tombeckbee Bank in St. Stephens, by then designated as the temporary capital of the new Alabama Territory.

Gaines negotiated the Treaty of Dancing Rabbit Creek between the United States and the Choctaw people, acquiring most of their lands in Alabama and Mississippi.