Reconstructing a robust species phylogeny and disentangling the evolutionary and biogeographic history of the gymnosperm genus Ephedra, which has a large genome and rich polyploids, remain a big challenge. Here we reconstructed a transcriptome-based phylogeny of 19 diploid Ephedra species, and explored evolutionary reticulations in this genus represented by 50 diploid and polyploid species, using four low-copy nuclear and nine plastid genes. The diploid species phylogeny indicates that the Mediterranean species diverged first, and the remaining species split into three clades, including the American species (Clade A), E. rhytidosperma, and all other Asian species (Clade B). The single-gene trees placed E. rhytidosperma sister to Clade A, Clade B, or Clades A + B in similar proportions, suggesting that radiation and gene flow likely occurred in the early evolution of Ephedra. In addition, reticulate evolution occurred not only among the deep nodes, but also in the recently evolved South American species, which further caused difficulty in phylogenetic reconstruction. Moreover, we found that allopolyploid speciation was pervasive in Ephedra. Our study also suggests that Ephedra very likely originated in the Tethys coast during the late Cretaceous, and the South American Ephedra species have a single origin by dispersal from Mexico or North America.