Agency began as a government trading post established to maintain contact with the Choctaw people. The post was located on Robinson Road, about east of the Noxubee River. Robinson Road connected the cities of Columbus, Jackson, and Natchez, and is the second oldest road in Mississippi. Government workers were employed at Agency as early as 1813, and Colonel Ward was in charge. Ward's house fronted the north side of Robinson Road, and consisted of two large rooms made of hewn logs. The cellar was made of brick, and was described as a "dungeon" used to confine fugitive slaves. Slaves who fled plantations in Mississippi and Alabama would seek asylum with the Choctaw people. The Choctaw, themselves slave owners, would deliver the fugitives to Colonel Ward, who would lock them in stocks in his cellar. The early settlement also had a storehouse, blacksmith shop, and stables. The agency house was abandoned in 1832, and the building was demolished in the 1840s. The Choctaw council house was situated on the east bank of Noxubee river, about southeast of Agency, just north of the county line. The place later became known as "Council Bluff". By the 1850s, Agency had flourished as a stagecoach stop, and had exceeded nearby Starkville in trade. Jefferson Davis spoke at the community center in Agency in the 1850s. Agency had a school, a post office by 1854, a Masonic Grand Lodge from 1861 to 1872, and one of Oktibbeha County's three "dens" of the Ku Klux Klan. John J. Walker and his wife Marie lived in Agency during the mid-1800s. A letter addressed to "Mrs. John J. Walker, Choctaw Agency, Oktibbeha County, Mississippi" has been preserved in the archive at Mississippi State University Library. The stamped envelope, however, was made public and sold for $21,000. By 1870, Agency had a population of 4,170 people. Around that time, the Mobile and Ohio Railroad completed a line east of Agency. Without railway access, the town's prosperity was undermined, and by 1887, Agency's last store closed. In 1894, its last doctor moved to Starkville. By 1900, Agency had a population of 30, and in 1905, its post office closed. Agency today is covered by forest, and there are some homes on Robinson Road.
