Valuable insights into the history of human populations have been obtained by studying the genetic composition of their domesticated species. Here we address some of the long-standing questions about the origin and subsequent movements of goat pastoralism in Northern Africa. We present the first study combining results from mitochondrial DNA (mtDNA) and Y chromosome loci for the genetic characterization of a domestic goat population. Our analyses indicate a remarkably high diversity of maternal and paternal lineages in a sample of indigenous goats from the northwestern fringe of the African continent. Median-joining networks and a multidimensional scaling of ours and almost 2000 published mtDNA sequences revealed a considerable genetic affinity between goat populations from the Maghreb (Northwest Africa) and the Near East. It has been previously shown that goats have a weak phylogeographic structure compatible with high levels of gene flow, as demonstrated by the worldwide dispersal of the predominant mtDNA haplogroup A. In contrast, our results revealed a strong correlation between genetic and geographical distances in 20 populations from different regions of the world. The distribution of Y chromosome haplotypes in Maghrebi goats indicates a common origin for goat patrilines in both Mediterranean coastal regions. Taken together, these results suggest that the colonization and subsequent dispersal of domestic goats in Northern Africa was influenced by the maritime diffusion throughout the Mediterranean Sea and its coastal regions of pastoralist societies whose economy included goat herding. Finally, we also detected traces of gene flow between goat populations from the Maghreb and the Iberian Peninsula corroborating evidence of past cultural and commercial contacts across the Strait of Gibraltar.