Low cardiorespiratory fitness is a powerful predictor of morbidity and cardiovascular mortality. In 473 sedentary adults, all whites, from 99 families of the Health, Risk Factors, Exercise Training, and Genetics (HERITAGE) Family Study, the heritability of gains in maximal O₂ uptake (V̇o_2max) after exposure to a standardized 20-wk exercise program was estimated at 47%. A genome-wide association study based on 324,611 single-nucleotide polymorphisms (SNPs) was undertaken to identify SNPs associated with improvements in V̇o_2max Based on single-SNP analysis, 39 SNPs were associated with the gains with P < 1.5 × 10⁻⁴. Stepwise multiple regression analysis of the 39 SNPs identified a panel of 21 SNPs that accounted for 49% of the variance in V̇o_2max trainability. Subjects who carried ≤9 favorable alleles at these 21 SNPs improved their V̇o_2max by 221 ml/min, whereas those who carried ≥19 of these alleles gained, on average, 604 ml/min. The strongest association was with rs6552828, located in the acyl-CoA synthase long-chain member 1 ( ACSL1) gene, which accounted by itself for ∼6% of the training response of V̇o_2max. The genes nearest to the SNPs that were the strongest predictors were PR domain-containing 1 with ZNF domain ( PRDM1); glutamate receptor, ionotropic, N-methyl-d-aspartate 3A ( GRIN3A); K⁺ channel, voltage gated, subfamily H, member 8 ( KCNH8); and zinc finger protein of the cerebellum 4 ( ZIC4). The association with the SNP nearest to ZIC4 was replicated in 40- to 65-yr-old, sedentary, overweight, and dyslipidemic subjects trained in Studies of a Targeted Risk Reduction Intervention Through Defined Exercise (STRRIDE; n = 183). Two SNPs were replicated in sedentary obese white women exercise trained in the Dose Response to Exercise (DREW) study ( n = 112): rs1956197 near dishevelled associated activator of morphogenesis 1 ( DAAM1) and rs17117533 in the vicinity of necdin ( NDN). The association of SNPs rs884736 in the calmodulin-binding transcription activator 1 ( CAMTA1) locus and rs17581162 ∼68 kb upstream from regulator of G protein signaling 18 ( RGS18) with the gains in V̇o_2max in HERITAGE whites were replicated in HERITAGE blacks ( n = 247). These genomic predictors of the response of V̇o_2max to regular exercise provide new targets for the study of the biology of fitness and its adaptation to regular exercise. Large-scale replication studies are warranted.