Parallel evolution provides strong evidence of adaptation by natural selection due to local environmental variation. Yet, the chronology, and mode of the process of parallel evolution remains debated. Here, we harness the temporal resolution of paleogenomics to address these long-standing questions, by comparing genomes originating from the mid-Holocene (8610-5626 years before present, BP) to contemporary pairs of coastal-pelagic ecotypes of bottlenose dolphin. We find that the affinity of ancient samples to coastal populations increases as the age of the samples decreases. We assess the youngest genome (5626 years BP) at sites previously inferred to be under parallel selection to coastal habitats and find it contained coastal-associated genotypes. Thus, coastal-associated variants rose to detectable frequencies close to the emergence of coastal habitat. Admixture graph analyses reveal a reticulate evolutionary history between pelagic and coastal populations, sharing standing genetic variation that facilitated rapid adaptation to newly emerged coastal habitats.