Sperm competition, the contest among ejaculates from rival males to fertilize ova of a female, is a common and powerful evolutionary force influencing ejaculate traits. During competitive interactions between ejaculates, longer and faster spermatozoa are expected to have an edge; however, to date, there has been mixed support for this key prediction from sperm competition theory. Here, we use the spectacular radiation of cichlid fishes from Lake Tanganyika to examine sperm characteristics in 29 closely related species. We provide phylogenetically robust evidence that species experiencing greater levels of sperm competition have faster-swimming sperm. We also show that sperm competition selects for increases in the number, size, and longevity of spermatozoa in the ejaculate of a male, and, contrary to expectations from theory, we find no evidence of trade-offs among sperm traits in an interspecific analysis. Also, sperm swimming speed is positively correlated with sperm length among, but not within, species. These different responses to sperm competition at intra- and interspecific levels provide a simple, powerful explanation for equivocal results from previous studies. Using phylogenetic analyses, we also reconstructed the probable evolutionary route of trait evolution in this taxon, and show that, in response to increases in the magnitude of sperm competition, the evolution of sperm traits in this clade began with the evolution of faster (thus, more competitive) sperm.