Noxubee county was a part of the Choctaw Indian Nation. On September 27, 1830, the Choctaw Indians signed the Treaty of Dancing Rabbit Creek ceding much of their Mississippi lands to the United States. The site of the treaty signing ceremony lies within Noxubee County. Twenty-five counties, including Noxubee, eventually were formed on the lands ceded to the United States under this treaty. A point near the center of the county was chosen as the seat of the government; the town became into existence on March 4, 1834, and was named Macon in honor of U.S. Senator Nathaniel Macon of North Carolina who was very outstanding at the time, being a close friend and political ally of Thomas Jefferson. The town was incorporated in 1836 and immediately became a trading center for the sorrounding territory.

On June 2, 1835, a temporary courthouse was completed at a cost of $620. In 1840, the county's first brick courthouse was constructed. The third courthouse was completed just prior to the Civil War at a cost of approximately $60,000.

The county's early settlers were farmers practicing the plantation system of farming, with cotton being the main crop. Among the county's early industries were several grain and lumber mills. In 1849, the Macon Beacon was established. Although it was not the first newspaper in the county, it is notable for having continued in operations to this day.

In 1856, the railroad came to Noxubee County when the Mobile and Ohio Railroad completed a line which ran north-south through the county.

On August 6, 1863, and with Jackson under attack, the state capitol was moved temporarily to Macon where it remained until the surrender and the subsequent arrest by federal authorities of Governor Clark at Appomatox. Several improvised hospitals were maintained in Macon during the Civil War; the largest was locatd in the building of the Calhoun Institute, which also housed the executive offices of Governor Clark and accommodated the Legislature during the two sessions held in Macon.

At the height of the Civil War, the capital of the Confederacy was moved to Macon, being located in the basement of the old Methodist Church. There were no significant battles fought in Noxubee County. However, Macon is the site of a Civil War cemetery. Many soldiers wounded in the Battle of Siloh were brought to Macon for treatment, and many of them died there and were buried in the local Odd Fellows Cemetery.

Early in its history, Macon became an educational center of more than state-wide importance. Among the many schools in and around Macon between 1850 and 1875 were Calhoun Institute, a girls school, established in 1856; Summerville Institute, a boys school, established in 1857 at Summerville, ten miles from Macon; Macon Female Seminary established in 1865; Galloway Institute, a girls school, established in 1876. In 1882, Noxubee County's first public school was opened in Macon.

Noxubee County's fourth courthouse was built in 1890 at a cost of under $25,000, replacing the 1860 courthouse which was torn down. The courthouse built in 1900 burned in 1951, and the present courthouse was built on the same site at a cost of over $350,000.