The Appomattoc were affiliated with the estimated 30 tribes of the Powhatan Confederacy, who controlled the area then known as Tenakomakah, present-day Tidewater Virginia.
The Appomattoc first encountered English explorers on May 8, 1607, when a party led by Christopher Newport reached one of their villages at the mouth of the Appomattox River (it was shown as "Mattica" on the 1608 Tindall map).
The English recorded that the foremost warrior among the Virginia Indians was bearing a bow and arrow in one hand, and a pipe with tobacco in the other, to signify the choice of war or peace.
Despite welcoming the colonists, some Appomattoc warriors took part in the sporadic raids on their fort until June 13, after which the paramount Chief Powhatan called a ceasefire.
Around Christmas 1611, in reprisal for an Appomattoc ambush on a group of English colonists a year before, Sir Thomas Dale seized Oppussoquionuske's village and the surrounding cultivated land.
Following the resumption of hostilities in 1622, the colonists, led by Captain Nathaniel West, destroyed Coquonasum's village and drove off the residents in August 1623.
Following the treaty of 1646, and until 1691, this fort marked the legal frontier of white settlement, which ran in a straight line from the "head of Yapin" (modern Franklin, Virginia) to the Monacan town on the James River (west of where Richmond is now).
At first the Virginia Indians had to wear a badge made of striped cloth while in white territory to show they were authorized, or they could be murdered on the spot.
In 1671, their weroance Peracuta led Thomas Batts and Robert Fallam on an expedition within the borders of present-day West Virginia.
[4] In 1705, Robert Beverley, Jr. noted that the Appomattoc consisted of no more than seven families, living on the pasture of William Byrd II at Westover Plantation.
The names "Appomattox" and "Mattox" were sometimes applied to the Matchotic, a Virginia Indian group made up of the Onawmanient and other remnant tribes of the Powhatan Confederacy, but located principally in the Northern Neck region between the Potomac and Rappahannock rivers.