Monumental architecture is a prime indicator of social complexity, because it requires many people to build a conspicuous structure commemorating shared beliefs. Examining monumentality in different environmental and economic settings can reveal diverse reasons for people to form larger social units and express unity through architectural display. In multiple areas of Africa, monumentality developed as mobile herders created large cemeteries and practiced other forms of commemoration. The motives for such behavior in sparsely populated, unpredictable landscapes may differ from well-studied cases of monumentality in predictable environments with sedentary populations. Here we report excavations and ground-penetrating radar surveys at the earliest and most massive monumental site in eastern Africa. Lothagam North Pillar Site was a communal cemetery near Lake Turkana (northwest Kenya) constructed 5,000 years ago by eastern Africa’s earliest pastoralists. Inside a platform ringed by boulders, a 119.5-m2 mortuary cavity accommodated an estimated minimum of 580 individuals. People of diverse ages and both sexes were buried, and ornaments accompanied most individuals. There is no evidence for social stratification. The uncertainties of living on a “moving frontier” of early herding—exacerbated by dramatic environmental shifts—may have spurred people to strengthen social networks that could provide information and assistance. Lothagam North Pillar Site would have served as both an arena for interaction and a tangible reminder of shared identity.