Maximal oxygen uptake (VO_2max) and the amount of type 1 fibers are interrelated but the underlying unifying molecular mechanisms are poorly understood. To explore these mechanisms we related gene expression profiles in skeletal muscle biopsies of 43 age-matched men from published datasets with VO_2max and amount of type 1 fibers and replicated some of the findings in muscle biopsies from 154 young and elderly individuals using real-time PCR. We identified 66 probesets (genes or ESTs) positively and 83 probesets inversely correlated with VO_2max and 171 probesets positively and 217 probesets inversely correlated with percentage of type 1 fibers in human skeletal muscle. Genes involved in oxidative phosphorylation (OXPHOS) showed high expression in individuals with high VO_2max whereas the opposite was not the case in individuals with low VO_2max. Instead, genes like AHNAK and BCL6 were associated with low VO_2max. Also, expression of the OXPHOS genes NDUFB5 and ATP5C1 increased with exercise training and decreased with aging. In contrast, expression of AHNAK in skeletal muscle decreased with exercise training and increased with aging. Eleven genes (NDUFB4, COX5A, UQCRB, ATP5C1, ATP5G3, ETHE1, FABP3, ISCA1, MYST4, C9orf3 and PKIA) were positively correlated with both VO_2max and percentage of type 1 fibers. VO_2max closely reflects expression of OXPHOS genes, particularly of NDUFB5 and ATP5C1 in skeletal muscle suggesting good muscle fitness. In contrast, a high expression of AHNAK was associated with a low VO_2max and poor muscle fitness.