Before 1835, Hanover County's only jail was a "small structure with a steeply pitched roof" to the southeast of the courthouse. This jail was reportedly relatively comfortable, with a stove for heat, but insecure.
What is today known as the Old Stone Jail was built around 1835, likely using stone from the quarry at Aquia, Virginia (although local lore has it that the stone came from the South Anna River). By 1841 both jails were being used by the county: The older jail as a debtor's prison, and the new stone jail for holding criminals and runaway slaves. The county's original jail was out of service by 1844, leaving the stone jail to handle all imprisonment.
Two cells, about fourteen feet square, occupy the Old Stone Jail's lower floor. Each cell had two windows secured with iron bars, but without shutters or glazing: This made for unpleasant conditions in the winter months, as inmates were not provided with bedding of any sort. The upper floor comprises one cell and a room that housed the jail's warden and his men.