On the basis of morphological differences, three subspecies of Black-tailed Godwit (Limosa limosa) have been recognized (L. l. limosa, L. l. islandica and L. l. melanuroides). In previous studies mitochondrial DNA (mtDNA) sequence data showed minimal genetic divergence between the three subspecies and an absence of sub-structuring within L. l. limosa. Here, population genetic structure and phylogeographic patterns have been analyzed using COI, HVR1 and HVR2 mtDNA sequence data as well as 12 microsatellite loci (nuDNA). The nuDNA data suggest genetic differentiation between L. l. limosa from Sweden and The Netherlands, between L. l. limosa and L. l. islandica, but not between L. l. limosa and L. l. melanuroides. However, the mtDNA data were not consistent with the nuDNA pattern. mtDNA did support a split between L. l. melanuroides and L. l. limosa/L. l. islandica and also demonstrated two L. l. limosa haplotype clusters that were not geographically isolated. This genetic structure can be explained by a scenario of isolation of L. l. melanuroides from L. l. limosa in Beringia during the Last Glacial Maximum. During the Pleistocene separation of L. l. islandica from L. l. limosa occurred, followed by colonization of Iceland by the L. l. islandica during the Holocene. Within L. l. limosa founder events, followed by population expansion, took place during the Holocene also. According to the patterns observed in both markers together and their geographic separation, we propose that the three traditional subspecies indeed represent three separate genetic units.