A few months ago, ancient DNA from a group of Neanderthals in a collapsed cave in France suggested it. Now, stronium levels in the teeth of pre-Neanderthals from Southern Africa suggest it. Indeed in all known cases where a determination can be made, admittedly a small data set, archaic hominins appear to have been patrilocal. Sons were part of the same communities as their fathers. Daughters joined the communities of their mates. This is also apparently the pattern of chimpanzee of our closest non-hominin primate relatives.
This has been observed in group burials of copper age peoples in Southern France from about 3000 BCE in a study released within the last month, and in Bronze Age ancient DNA from racially West Eurasian and probably linguistically Indo-European populations in Central Asia. But societies of modern humans (as opposed to Neanderthals or earlier proto-humans) about whom we have historical records are not uniform. Some have historically been patrilocal, some matrilocal, and some neither in any organized fashion. Most notably, hunter-gatherer societies in Africa right now are not patrilocal.