Abstract Background Males in some species of the genus Xiphophorus, small freshwater fishes from Meso-America, have an extended caudal fin, or sword – hence their common name “swordtails”. Longer swords are preferred by females from both sworded and – surprisingly also, non-sworded (platyfish) species that belong to the same genus. Swordtails have been studied widely as models in research on sexual selection. Specifically, the pre-existing bias hypothesis was interpreted to best explain the observed bias of females in presumed ancestral lineages of swordless species that show a preference for assumed derived males with swords over their conspecific swordless males. However, many of the phylogenetic relationships within this genus still remained unresolved. Here we construct a comprehensive molecular phylogeny of all 26 known Xiphophorus species, including the four recently described species (X. kallmani, X. mayae, X. mixei and X. monticolus). We use two mitochondrial and six new nuclear markers in an effort to increase the understanding of the evolutionary relationships among the species in this genus. Based on the phylogeny, the evolutionary history and character state evolution of the sword was reconstructed and found to have originated in the common ancestral lineage of the genus Xiphophorus and that it was lost again secondarily. Results We estimated the evolutionary relationships among all known species of the genus Xiphophorus based on the largest set of DNA markers so far. The phylogeny indicates that one of the newly described swordtail species, Xiphophorus monticolus, is likely to have arisen through hybridization since it is placed with the southern platyfish in the mitochondrial phylogeny, but with the southern swordtails in the nuclear phylogeny. Such discordance between these two types of markers is a strong indication for a hybrid origin. Additionally, by using a maximum likelihood approach the possession of the sexually selected sword trait is shown to be the most likely ancestral state for the genus Xiphophorus. Further, we provide a well supported estimation of the phylogenetic relationships between the previously unresolved northern swordtail groups. Conclusions This comprehensive molecular phylogeny of the entire genus Xiphophorus provides evidence that a second swordtail species, X. monticolus, arose through hybridization. Previously, we demonstrated that X. clemenciae, another southern swordtail species, arose via hybridization. These findings highlight the potential key role of hybridization in the evolution of this genus and suggest the need for further investigations into how hybridization contributes to speciation more generally.