Hybridization is increasingly being recognized as a widespread process, even between ecologically and behaviorally divergent animal species. Determining phylogenetic relationships in the presence of hybridization remains a major challenge for evolutionary biologists, but advances in sequencing technology and phylogenetic techniques are beginning to address these challenges. Here we reconstruct evolutionary relationships among swordtails and platyfishes (Xiphophorus: Poeciliidae), a group of species characterized by remarkable morphological diversity and behavioral barriers to interspecific mating. Past attempts to reconstruct phylogenetic relationships within Xiphophorus have produced conflicting results. Since many of the 26 species in the genus are interfertile, these conflicts are likely due to hybridization. Using genomic data, we resolve a high-confidence species tree of Xiphophorus that accounts for both incomplete lineage sorting and hybridization. Our results allow us to re-examine a long-standing controversy about the evolution of the sexually selected sword in Xiphophorus, and demonstrate that hybridization has been strikingly widespread in the evolutionary history of this genus.