Next‐generation reduced representation sequencing (RRS) approaches show great potential for resolving the structure of wild populations. However, the population structure of species that have shown rapid demographic recovery following severe population bottlenecks may still prove difficult to resolve due to high gene flow between subpopulations. Here, we tested the effectiveness of the RRS method Genotyping‐By‐Sequencing (GBS) for describing the population structure of the New Zealand fur seal (NZFS, Arctocephalus forsteri), a species that was heavily exploited by the 19th century commercial sealing industry and has since rapidly recolonized most of its former range from a few isolated colonies. Using 26,026 neutral single nucleotide polymorphisms (SNPs), we assessed genetic variation within and between NZFS colonies. We identified low levels of population differentiation across the species range (<1% of variation explained by regional differences) suggesting a state of near panmixia. Nonetheless, we observed subtle population substructure between West Coast and Southern East Coast colonies and a weak, but significant (p = 0.01), isolation‐by‐distance pattern among the eight colonies studied. Furthermore, our demographic reconstructions supported severe bottlenecks with potential 10‐fold and 250‐fold declines in response to Polynesian and European hunting, respectively. Finally, we were able to assign individuals treated as unknowns to their regions of origin with high confidence (96%) using our SNP data. Our results indicate that while it may be difficult to detect population structure in species that have experienced rapid recovery, next‐generation markers and methods are powerful tools for resolving fine‐scale structure and informing conservation and management efforts.