Populations and species are threatened by human pressure, but their fate is variable. Some depleted populations, like that of the northern elephant seal (Mirounga angustirostris), recover rapidly even when the surviving population was small. We sequenced 260 modern and 8 historical genomes to assess the impact of a severe population bottleneck on individual northern elephant seals and to better understand their recovery. We show that inbreeding, an increase in the frequency of alleles compromised by lost function, and allele frequency distortion reduced the fitness of breeding males and females, as well as the performance of adults on foraging migrations. We provide the first detailed investigation of the impact of a severe bottleneck on fitness at the genomic level, and report on the role of specific gene systems.