The later Holocene spread of pastoralism throughout eastern Africa profoundly changed socio-economic and natural landscapes. During the Pastoral Neolithic (ca. 5000–1200 B.P.), herders spread through southern Kenya and northern Tanzania—areas previously occupied only by hunter-gatherers—eventually developing the specialized forms of pastoralism that remain vital in this region today. Research on ancient pastoralism has been primarily restricted to rockshelters and special purpose sites. This paper presents results of surveys and excavations at Luxmanda, an open-air habitation site located farther south in Tanzania, and occupied many centuries earlier, than previously expected based upon prior models for the spread of herding. Technological and subsistence patterns demonstrate ties to northerly sites, suggesting that Luxmanda formed part of a network of early herders. The site is thus unlikely to stand alone, and further surveys are recommended to better understand the spread of herding into the region, and ultimately to southern Africa.