Present-day hunter-gatherers (HGs) live in multilevel social groups essential to sustain a population structure characterized by limited levels of within-band relatedness and inbreeding. When these wider social networks evolved among HGs is unknown. To investigate whether the contemporary HG strategy was already present in the Upper Paleolithic, we used complete genome sequences from Sunghir, a site dated to ~34,000 years before the present, containing multiple anatomically modern human individuals. We show that individuals at Sunghir derive from a population of small effective size, with limited kinship and levels of inbreeding similar to HG populations. Our findings suggest that Upper Paleolithic social organization was similar to that of living HGs, with limited relatedness within residential groups embedded in a larger mating network.