The Cedars began as a log cabin whose exact construction date and original owner are unknown but is believed to be c. 1830[2] and possibly as early as 1818.

Randolph was from Virginia and settled near Caledonia, Mississippi in 1825 on a plantation that he named Goshen.

Shortly before buying the McBee property, Randolph freed all of his slaves, sending any that wished to go to settle in Liberia.

[2] The original log cabin was single-pen, 21 foot square, and made of hewn pine.

[3] Randolph and his wife, Elizabeth Bland Beverley, made renovations in 1835–1836, elevating the roof-line an extending the gable end south to add a room.