Over the last century, many shark populations have declined, primarily due to overexploitation in commercial, artisanal and recreational fisheries. In addition, in some locations the use of shark control programs also has had an impact on shark numbers. Still, there is a general perception that populations of large ocean predators cover wide areas and therefore their diversity is less susceptible to local anthropogenic disturbance. Here we report on temporal genomic analyses of tiger shark (Galeocerdo cuvier) DNA samples that were collected from eastern Australia over the past century. Using Single Nucleotide Polymorphism (SNP) loci, we documented a significant change in genetic composition of tiger sharks born between ~1939 and 2015. The change was most likely due to a shift over time in the relative contribution of two well-differentiated, but hitherto cryptic populations. Our data strongly indicate a dramatic shift in the relative contribution of these two populations to the overall tiger shark abundance on the east coast of Australia, possibly associated with differences in direct or indirect exploitation rates.