William Strachey, an Englishman who lived at Jamestown from 1610 until 1611, recorded the naming practices of Algonquian-speaking Powhatans; the practices of other Indian-language groups in Virginia may have been similar but were not recorded. According to Strachey, the names of Virginia Indians had specific Algonquian meanings, most of which have been lost with the language. The Powhatans, and possibly other Virginia Indians, also took multiple names, sometimes simultaneously, beginning early in their lives. These multiple names did not follow the English pattern of first name, middle name, and surname, however. In fact, Strachey reports that the Powhatans were unaccustomed to English naming practices and often insisted on calling Englishmen by their first names only. Among the Powhatans, different names were reserved for different situations.

For example, Pocahontas had at least two names from her early days. Her proper, publicly given name was Amonute, which cannot be translated today. She also had a secret given name, Matoaka, which she revealed to the English only after she had taken another religious—baptismal—name, Rebecca. In some other American Indian societies, the secret name was so personal that an ill-disposed person, on learning it, could work sorcery by saying a spell with the name in it. Samuel Purchas, the English travel writer and editor who helped to publicize the Jamestown colony, wrote in a marginal note in his 1617 edition of Purchas, His Pilgrimes that Pocahontas and her family had been fearful that the English would harm her if they learned her private name.

Indian children also had nicknames. Bestowed by others, these names often changed over time and reflected personalities and experiences rather than being variants on birth names. "Pocahontas," for instance, was a childhood nickname, probably handed out by older relatives who were responsible for raising her. Strachey writes it means "little wanton"—and wanton in Strachey's time not only meant sexually bawdy; it also had overtones of cruel and undisciplined. By the time she was about eight, and due to the particular marriage customs instituted by her father, the paramount chief Powhatan, Pocahontas joined a huge household of stepmothers and half-siblings. Forced to compete for her busy father's attention, she possibly took to teasing him about his many wives, a practice that may have earned her her nickname.

Powhatan males, according to Strachey, were expected to earn new names that celebrated their exploits. From an early age, boys faced pressure to become proficient enough marksmen that their fathers would take them along on hunts. While a boy's mother continued to call him by an affectionate child's name, his father watched him perform on hunts and then bestowed a new young man's name. Other names might follow as his proficiency in hunting and war grew, and when the young man became initiated into manhood and then performed a truly outstanding feat as a warrior, the tribal chief gave him yet another name to memorialize his deeds. These names were not titles; they were personal names to be used in conversation.

Chiefs had multiple names, earned over the course of their lives, and when they became chiefs, they took on a new name to mark the occasion. Strachey does not say whether Powhatan, as paramount chief, bestowed on these newly made chiefs their new names, although he probably did. By 1607 Powhatan bore several adult names. Writes Strachey (in a modernized version of his text): The great Emperor at this time amongst them we Commonly call Powhatan for by that name true it is, he was made known to us, when we arrived in the Country first, and so indeed he was generally called when he was a young man, as taking his denomination from the Country Powhatan, wherein he was borne … the Inhabitants [native people] themselves, especially his frontier neighbor princes, call him still POWHATAN, his own people sometimes call him OTTANIACK, sometimes MAMANATOWICK, which last signifies great King, but his proper right name which they salute him with (himself in presence) is WAHUNSENACAWH.

The inference is that Wahunsenacawh (also written Wahunsunacock) was Powhatan's most-recent personal name.

Paramount chiefs were known to take new names even late in life. Powhatan's successors, his two younger brothers Opitchapam (or Otiotan) and Opechancanough, did so in mid-1621, when they were in their seventies. The English colonists noted the practice in passing and lost interest—to their cost. The first strike in the Second Anglo-Powhatan War (1622–1632), a widespread group of attacks on a single morning by the Powhatans against the Jamestown colonists, was originally planned for the fall of 1621, and the leaders' name changes may well have reflected the completion of their preparations. A last-minute leak of the plans led to the attack being postponed.

Virginia Indians began adopting English first names after the middle of the seventeenth century. In the 1680s, a small number of Indian children who went to work for English farmers were given English first names, and in some county records both names were recorded. By 1700 some Indian elders took on English first names, sometimes paired with shortened Indian surnames, to be used when dealing with non-Indians and possibly even among themselves. By 1750, however, most Powhatan people, at least, had English first and surnames that they apparently used full-time.

The best records are from the Pamunkey Reservation. Between about 1720 and 1840, all letters and petitions to the Virginia government were signed by all the adult men of the tribe. After about 1740 no Indian-language surnames appear in these Pamunkey documents, and every signer had first and last names in English; several of those names given by 1790 are still held by reservation residents today.