The Eastern Chickahominy share an early history with the, who, despite their similar language and culture, lived independently of the Indians of . In 1614, following the (1609–1614), they become tributary allies of the , and in 1646, following the Third Anglo-Powhatan War (1644–1646), joined other Virginia Indians living in the Pamunkey Neck area of present-day King William County. By 1820, families with present-day Chickahominy surnames had begun to settle in Charles City County. In 1870, a state census reported a group of Indians living in New Kent County; these are likely the ancestors of the present-day Eastern Chickahominy Indians.
Chickahominy Indians in the Windsor Shades–Boulevard area of New Kent County established a school in 1910. In 1920–1921, they formally organized themselves as a separate tribal government, with E. P. Bradby the first chief. Some have argued that the distance between the New Kent and Charles City tribal centers—amounting to twenty miles round trip—occasioned the split, while others have cited church issues and a disagreement over the creation of a reservation (the western faction opposed a reservation, while the eastern faction supported it). In September 1922 the Tsena Commocko Indian Baptist Church was organized. In 1925, Virginia issued the tribe a certificate of incorporation.
Like other Virginia Indians, the Eastern Chickahominy struggled to preserve their identity and culture early in the twentieth century. Theand subsequent legislation banned interracial marriage in Virginia and asked for voluntary racial identifications on birth and marriage certificates. “White” was defined as having no trace of African ancestry, while all other people, including Indians, were defined as “colored.” To accommodate elite Virginians who claimed and as ancestors, the law allowed for those who had “one-sixteenth or less of the blood of the American Indian and have no other non-Caucasic blood [to] be deemed to be white persons.” The law essentially erased Virginia Indians as a category of people.
By late in the century, however, the tribes had reasserted their identity. On March 25, 1983, Virginia Joint Resolution 54 officially recognized the Eastern Chickahominy Tribe. The tribe was federally recognized on January 29, 2018.