A low maximal oxygen consumption (V̇o2max) is a strong risk factor for premature mortality. Supervised endurance exercise training increases V̇o2max with a very wide range of effectiveness in humans. Discovering the DNA variants that contribute to this heterogeneity typically requires substantial sample sizes. In the present study, we first use RNA expression profiling to produce a molecular classifier that predicts V̇o2max training response. We then hypothesized that the classifier genes would harbor DNA variants that contributed to the heterogeneous V̇o2max response. Two independent preintervention RNA expression data sets were generated ( n = 41 gene chips) from subjects that underwent supervised endurance training: one identified and the second blindly validated an RNA expression signature that predicted change in V̇o2max (“predictor” genes). The HERITAGE Family Study ( n = 473) was used for genotyping. We discovered a 29-RNA signature that predicted V̇o2max training response on a continuous scale; these genes contained ∼6 new single-nucleotide polymorphisms associated with gains in V̇o2max in the HERITAGE Family Study. Three of four novel candidate genes from the HERITAGE Family Study were confirmed as RNA predictor genes (i.e., “reciprocal” RNA validation of a quantitative trait locus genotype), enhancing the performance of the 29-RNA-based predictor. Notably, RNA abundance for the predictor genes was unchanged by exercise training, supporting the idea that expression was preset by genetic variation. Regression analysis yielded a model where 11 single-nucleotide polymorphisms explained 23% of the variance in gains in V̇o2max, corresponding to ∼50% of the estimated genetic variance for V̇o2max. In conclusion, combining RNA profiling with single-gene DNA marker association analysis yields a strongly validated molecular predictor with meaningful explanatory power. V̇o2max responses to endurance training can be predicted by measuring a ∼30-gene RNA expression signature in muscle prior to training. The general approach taken could accelerate the discovery of genetic biomarkers, sufficiently discrete for diagnostic purposes, for a range of physiological and pharmacological phenotypes in humans.