The human populations of the Iberian Peninsula are the varied result of a complex mixture of cultures throughout history, and are separated by clear social, cultural, linguistic or geographic barriers. The stronger genetic differences between closely related populations occur in the northern third of Spain, a phenomenon commonly known as "micro-differentiation". It has been argued and discussed how this form of genetic structuring can be related to both the rugged landscape and the ancient societies of Northern Iberia, but this is difficult to test in most regions due to the intense human mobility of previous centuries. Nevertheless, the Spanish autonomous community of Asturias shows a complex history which hints of a certain isolation of its population. This, joined together with a difficult terrain full of deep valleys and steep mountains, makes it suitable for performing a study of genetic structure, based on mitochondrial DNA and Y-Chromosome markers. Our analyses do not only show that there are micro-differentiation patterns inside the Asturian territory, but that these patterns are strikingly similar between both uniparental markers. The inference of barriers to gene flow also indicates that Asturian populations from the coastal north and the mountainous south seem to be relatively isolated from the rest of the territory. These findings are discussed in light of historic and geographic data and, coupled with previous evidence, show that the origin of the current genetic patterning might indeed lie in Roman and Pre-Roman sociopolitical divisions.