The early Iron Age (800 to 450 BCE) in France, Germany and Switzerland, known as the ‘West-Hallstattkreis’, stands out as featuring the earliest evidence for supra-regional organization north of the Alps. Often referred to as ‘early Celtic’, suggesting tentative connections to later cultural phenomena, its societal and population structure remain enigmatic. Here we present genomic and isotope data from 31 individuals from this context in southern Germany, dating between 616 and 200 BCE. We identify multiple biologically related groups spanning three elite burials as far as 100 km apart, supported by trans-regional individual mobility inferred from isotope data. These include a close biological relationship between two of the richest burial mounds of the Hallstatt culture. Bayesian modelling points to an avuncular relationship between the two individuals, which may suggest a practice of matrilineal dynastic succession in early Celtic elites. We show that their ancestry is shared on a broad geographic scale from Iberia throughout Central-Eastern Europe, undergoing a decline after the late Iron Age (450 BCE to ~50 CE).