The Ephedra lineage can be traced at least to the Early Cretaceous. Its characteristically polyplicate pollen is well-represented in the fossil record and is frequently used as an indicator of paleoclimate. However, despite previous efforts, knowledge about variation and evolution of ephedroid pollen traits is poor. Here, we document pollen morphology of nearly all extant species of Ephedra, using a combination of scanning electron microscopy (SEM) and light microscopy (LM), and reconstruct ancestral states of key pollen traits. Our results indicate that the ancestral Ephedra pollen type has numerous plicae interspaced by unbranched pseudosulci, while the derived pollen type has branched pseudosulci and (generally) fewer plicae. The derived type is inferred to have evolved independently twice, once along the North American stem branch and once along the Asian stem branch. Pollen of the ancestral type is common in Mesozoic fossil records, especially from the Early Cretaceous, but it is less commonly reported from the Cenozoic. The earliest documentation of the derived pollen type is from the latest Cretaceous, after which it increases strongly in abundance during the Paleogene. The results of the present study have implications for the age of crown group Ephedra as well as for understanding evolution of pollination syndromes in the genus.