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 in Mississippi.
[1] A portion of the road appeared on an 1831 map of Mississippi that illustrated the "Gaines Road" extending from Russellville, Alabama to Cotton Gin Port.
[2] Jackson's Military Road, constructed from 1816 to 1820, intersected Gaines Trace in Russellville.
Tennessee Street in Courtland, Alabama, was a portion of the Trace.