We analysed more than 600 red deer (Cervus elaphus) from large parts of its European distribution range at 13 microsatellite loci, presenting the first continent-wide study of this species using nuclear markers. Populations were clearly differentiated (overall FST = 0.166, Jost’s Dest = 0.385), and the BAPS clustering algorithm yielded mainly geographically limited and adjacent genetic units. When forced into only three genetic clusters our data set produced a very similar geographic pattern as previously found in mtDNA phylogeographic studies: a western group from Iberia to central and parts of Eastern Europe, an eastern group from the Balkans to Eastern Europe and a third group including the threatened relict populations from Sardinia and Mesola in Italy. This result was also confirmed by a multivariate approach to analysing our data set, a discriminant analysis of principal components (DAPC). Calculations of genetic diversity and effective population sizes (linkage-disequilibrium approach) yielded the lowest results for Italian (Sardinia, Mesola; Ne between two and eight) and Scandinavian red deer, in line with known bottlenecks in these populations. Our study is the first to present comparative nuclear genetic data in red deer across Europe and may serve as a baseline for future analyses of genetic diversity and structuring in this widespread ungulate.