Accomack County was named for the Accomac Indians, who lived on the Eastern Shore at the time of the first English settlement in Virginia. The word means "on-the-other-side-of-water place" or "across the water." It was one of the original eight shires, or counties, first enumerated in 1634 and spelled Accomac without the k. The county's name was changed to Northampton County in 1643. The present county was formed from Northampton about 1663. In October 1670, the General Assembly temporarily reunited Accomack and Northampton Counties as Northampton County. In November 1673, Accomack County was again separated from Northampton. In early records, the county's name was spelled many ways. In 1940 the General Assembly adopted the present spelling, Accomack. The county gained a small part of the southern end of Smith's Island from Somerset County, Maryland, in 1879, after the United States had approved boundary changes between Virginia and Maryland that had been agreed to in 1877. The county seat is Accomac.

A significant number of loose records from the 1700s suffered extreme water and pest damage. Volumes that record deeds, court orders, and wills exist.

The 1902 voter registration books were created following the passage of the 1902 Virginia state constitution. The purpose of the 1902 state constitution was to maintain white suffrage while eliminating African-American voters by means of literacy tests as well as property and poll tax requirements.