The Gaines Trace was a road in the Mississippi Territory. It was constructed in 1811 and 1812 from the Tennessee River (opposite the Elk River's mouth) to Cotton Gin Port on the upper Tombigbee River and on to Fort Stoddert on the lower Tombigbee. The portion from the Tennessee River to Cotton Gin Port was surveyed in 1807 and 1808 by Edmund P. Gaines, the road's namesake and a career United States Army officer. In 1816, the Gaines Trace and the Tombigbee River were the boundaries between United States and Chickasaw territory.