Genetic differences between human populations are typically larger for the Y-chromosome than for mitochondrial DNA (mtDNA), which has been attributed to the ubiquity of patrilocality across human cultures. However, this claim has been disputed, and previous analyses of matrilocal groups give conflicting results. Here we analyse mtDNA variation (complete mtDNA genome sequences via next-generation sequencing) and non-recombining regions of the Y-chromosome variation (Y-single-nucleotide-polymorphisms and Y-short-tandem-repeats (STR)) in a matrilocal group (the Semende) and a patrilocal group (the Besemah) from Sumatra. We find in the Semende significantly lower mtDNA diversity than in the Besemah as expected for matrilocal groups, but unexpectedly we find no difference in Y-chromosome diversity between the groups. We highlight the importance of using complete mtDNA sequences for such analyses, as using only partial sequences (as done in previous studies) can give misleading results.