Female multiple mating provides the opportunity for sexual selection to continue after gamete release, generating strong selection on male reproductive traits. In particular, in species where female multiple mating is common, males are expected to invest more in testicular tissue to afford them a numerical advantage during sperm competition. However, although testes size (correcting for body size) is a commonly used proxy of the strength of sperm competition, there is surprisingly scant direct evidence linking male investment in testes with genetic estimates of multiple paternity across species. Here we test the hypothesis that testes size is influenced by genetic estimates of sperm competition risk (multiple paternity percentage) and intensity (number of sires per brood) in fishes, the most diverse and specious vertebrate group. We provide conclusive evidence that testes size is larger in species experiencing a higher risk and intensity of sperm competition, a finding that remains consistent among sharks and bony fishes (including in separate analyses focused only on cichlids). These findings shed new light on evolutionary processes governing sperm competition in a basal vertebrate lineage and validate the now-widespread use of body-size corrected testes mass as a proxy for sperm competition risk and intensity.