John Henderson, a Presbyterian missionary and the town's namesake, settled in the area in 1798.[2]
In 1833, the Mississippi Legislature authorized the formation of 17 counties, including Yalobusha. Yalobusha County's first elected officials, called the "Board of Police", met in 1834 at Hendersonville. A county seat had not yet been selected, and the Board of Police solicited land donations. At the second meeting, a nearby location more centrally located in the county, later named Coffeeville, was selected for the county seat.[2][3] A local resident, Capt. L. Lake, wrote in 1834: "Hendersonville then went down and ultimately lost its name, being absorbed in a farm known as 'Oakchickamau,'" owned by Franklin E. Plummer.
An early resident of county named Mr. E. Percy Howe, appeared to dislike both Hendersonville and Coffeeville. He left a poem behind after moving away:
Upon a hill near Derden's Mill
There is a place called Coffeeville;
The meanest town I ever saw
Save Plummer's town, 'Oakchickamau.'[3]
