The plant family Myrtaceae is represented in the Paleogene-Neogene fossil pollen record by the genus Myrtaceidites. We review each formally described Myrtaceidites morphospecies and update fossil-extant affinities based on a comprehensive analysis of extant Myrtaceae genera pollen morphotypes and the recent tribal phylogenetic classification of Myrtaceae. New images of Myrtaceidites morphotypes preserved in Paleocene to Pliocene sediments are used to illustrate the morphological variation observed in each formally described Australian morphospecies. We propose M. rhodamnoides and M. verrucosus are variants (forma) of the same morphospecies viz. Myrtaceidites verrucosus forma rhodamnoides and M. verrucosus forma verrucosus, respectively. A new Myrtaceidites morphospecies, M. leptospermoides, is erected to represent fossil pollen with syncolporate colpi and a granulate exine pattern. Our review identifies nine distinct Myrtaceidites morphotypes and puts forward six, which we believe could be used as molecular dating calibrations. Myrtaceae genera from eastern and western Australia: Verticordia, Chamelaucium, Darwinia, and Homoranthus produce an acolpate pollen morphotype that has not been identified in the fossil record. We illustrate this type in the hope that this information will lead to its identification and subsequent naming in the fossil record.