Mayes was born on October 2, 1833 in present-day Carterville, Bartow County, Georgia to the former Nancy Adair (b. 1808, and part-Cherokee) and her husband Samuel Mayes (1803-1858, and adopted into the Cherokee tribe upon his marriage in 1825). In 1838, Samuel Mayes and his family (as well as the Adair family and others of mixed Scots/Irish and Cherokee ancestry and their slaves), relocated across the Mississippi River into what was then Indian Territory. Many of these "Old Settlers" had signed a removal treaty (the Treaty of New Echota) which many other Cherokee (including chief John Ross) abhorred and renounced. Samuel Mayes bred and sold livestock, and also owned many enslaved persons before his death in 1858 in what eventually became Mayes County, Oklahoma (named for him and/or his son after statehood five decades later).