The Iberian Peninsula is linguistically diverse and has a complex demographic history, including a centuries-long period of Muslim rule. Here, we study the fine-scale genetic structure of its population, and the genetic impacts of historical events, leveraging powerful, haplotype-based statistical methods to analyse 1413 individuals from across Spain. We detect extensive fine-scale population structure at extremely fine scales (below 10 Km) in some regions, including Galicia. We identify a major east-west axis of genetic differentiation, and evidence of historical north to south population movement. We find regionally varying fractions of north-west African ancestry (0-11%) in modern-day Iberians, related to an admixture event involving European-like and north-west African-like source populations. We date this event to 860-1120 CE, implying greater genetic impacts in the early half of Muslim rule in Iberia. Together, our results indicate clear genetic impacts of population movements associated with both the Muslim conquest and the subsequent Reconquista.