Community differentiation is a fundamental topic of the social sciences, and its prehistoric origins in Europe are typically assumed to lie among the complex, densely populated societies that developed millennia after their Neolithic predecessors. Here we present the earliest, statistically significant evidence for such differentiation among the first farmers of Neolithic Europe. By using strontium isotopic data from more than 300 early Neolithic human skeletons, we find significantly less variance in geographic signatures among males than we find among females, and less variance among burials with ground stone adzes than burials without such adzes. From this, in context with other available evidence, we infer differential land use in early Neolithic central Europe within a patrilocal kinship system.