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.

Accomack County is one of Virginia's Lost Records Localities. A significant number of loose records from the 1700s suffered extreme water and pest damage. Volumes that record deeds, court orders, and wills exist.

Two freeholders were appointed on order of the county court to procession or review the bounds of farms or tracts of land in each precinct in order to renew or replace old landmarks. This was originally a function of the church vestry, but was continued by the court after disestablishment. Persons who walked the boundaries were called processioners.