Phylogeographic studies of highly mobile large carnivores suggest that intra-specific genetic differentiation of modern species might be the consequence of the most recent Pleistocene glaciation. However, the relative influence of biogeographical processes and subsequent human-induced population fragmentation requires a better understanding. Poland represents the western edge of relatively continuous distributions of many wide-ranging species, e.g. lynx (Lynx lynx), wolves (Canis lupus), moose (Alces alces) and, therefore, a key area for understanding historic and contemporary patterns of gene flow in central Europe. We examined wolf genetic structure in Poland and in a recently recolonized area in eastern Germany using microsatellite profiles (n = 457) and mitochondrial DNA sequencing (mtDNA, n = 333) from faecal samples. We found significant genetic structure and high levels of differentiation between wolves in the Carpathian Mountains and the Polish lowlands. Our findings are consistent with previously reported mtDNA subdivision between northern lowlands and southern mountains, and add new and concordant findings based on autosomal marker variation. Wolves in western Poland and eastern Germany showed limited differentiation from northeastern Poland. Although the presence of private alleles suggests immigration also from areas not sampled in this study, most individuals seem to be immigrants from northeastern Poland or their descendants. We observed moderate genetic differentiation between certain northeastern lowland regions separated by less than 50 km. Moreover, mtDNA results indicated a southeastern subpopulation near the border with Ukraine. The observed structure might reflect landscape fragmentation and/or ecological differences resulting in natal habitat-biased dispersal.