Evolutionary relationships in Ephedra are difficult to resolve, mainly because there are few informative characters in investigated loci and long distances to outgroups. We address these problems by using a large data set that includes information from seven plastid and nuclear loci and 204 vascular plants. The deepest divergences in Ephedra are weakly supported and differ by analytical method, but they indicate a basal grade of species distributed in the Mediterranean area. New World species are monophyletic, with a South American clade possibly nested within a North American clade. A mainly Asian clade comprises several well‐supported subgroups, of which some are endemic to restricted geographic regions in East or Central Asia; others have a broad distribution that may extend into Europe (E. distachya, E. major) and/or Africa (E. pachyclada–E. somalensis). Ephedra laristanica and E. somalensis are nested within other species, whereas the recognition of E. milleri as a separate species is supported. Our results provide another example of how exceptionally difficult it is to disentangle the early divergences of seed plants. Bayesian analysis strongly supports the “gnetifer” hypothesis, a result rarely found in the literature, but it conflicts with our results from only chloroplast data (“gne‐cup”) and with results of most maximum parsimony analyses (“Gnetales sister”).