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. Here, we investigate whether the contemporary HG strategy was already present in the Upper Paleolithic (UP), using complete genome sequences from Sunghir, a site dated to ~34 thousand years BP (kya) containing multiple anatomically modern human (AMH) individuals. Wedemonstrate 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 UP social organization was similar to that of living HGs, with limited relatedness within residential groups embedded in a larger mating network.