Human cognitive abilities inter-correlate to form a positive matrix, from which a large first factor, called "Spearman's g" or general intelligence, can be extracted. General intelligence itself is correlated with many important health outcomes including cardio-vascular function and longevity. However, the important evolutionary question of whether intelligence is a fitness-related trait has not been tested directly, let alone answered. If the correlations among cognitive abilities are part of a larger matrix of positive associations among fitness-related traits, then intelligence ought to correlate with seemingly unrelated traits that affect fitness--such as semen quality. We found significant positive correlations between intelligence and 3 key indices of semen quality: log sperm concentration (r = 0.15, p = 0.002), log sperm count (r = 0.19, p less than 0.001), and sperm motility (r = 0.14, p = 0.002) in a large sample of US Army Veterans. None was mediated by age, body mass index, days of sexual abstinence, service in Vietnam, or use of alcohol, tobacco, marijuana, or hard drugs. These results suggest that a phenotype-wide fitness factor may contribute to the association between intelligence and health. Clarifying whether a fitness factor exists is important theoretically for understanding the genomic architecture of fitness-related traits, and practically for understanding patterns of human physical and psychological health. (Contains 3 tables.)