Between the time the Spanish arrived in 1570 and the English came to stay in 1607, Powhatan established control over many - but not all - tribes east of the Fall Line.
The Algonquian-speaking tribes in Virginia are often treated as if they were all part of Powhatan's "paramount chiefdom." However, the Potomacks/Patowomeks, Dogue, and other groups north of the Rappahannock River were only marginally under Powhatan's control, or remained completely free from any obligation to pay taxes to him.
Powhatan inherited control (from his mother rather than his father, in accord with his cultural tradition) of just four to six tribes. He conquered another 30 or so, and exerted control over many Algonquian-speaking Native Americans in Virginia when the Godspeed, Discovery, and Susan Constant sailed between the capes at the mouth of the Chesapeake Bay.
Those Algonquian-speaking tribes were all located east of the Fall Line. Powhatan ruled between the Falls of the James (today the site of Richmond) and the Atlantic Ocean. Powhatan dominated tribes on the southern part of the Eastern Shore, which could be reached only by canoe until the Europeans brought the new technology of sailing ships. Powhatan's power extended south to the Blackwater River and today's Virginia Beach, and north to Potomac and Aquia Creeks.
North of the Rappahannock River, his control was weak. The Potomack/Patawomeck tribe, which lived at the mouth of Aquia Creek, rejected his control and sold Powhatan's daughter Pocahontas to the English in 1613. She had been in the area ensuring the corn tax would be paid to her father, but ended up instead as a captive sold for a copper kettle.
Further north in Virginia, from the Occoquan River to the Little Falls of the Potomac River, Powhatan exerted no power. He tried to block the English from dealing with those tribes outside his control, so Powhatan could set prices and keep the Jamestown settlement dependent upon him. The Algonquian-speaking Dogue (also known as Taux or Dogues) were allied to Piscataway and other Maryland tribes rather than to Powhatan. The capital of their leader ("tayac") was located in Maryland.
Many of the place names of Virginia are based on the place names used by the Algonquian tribes, such as Chesapeake and Occoquan and Accomack. Such names are common east of the Fall Line, but tribes belonging to the Siouan and Iroquoian linguistic groups dominated the area west of the Fall Line.