Heliozelidae are a widespread, evolutionarily early diverging family of small, day-flying monotrysian moths, for which a comprehensive phylogeny is lacking. We generated the first molecular phylogeny of the family using DNA sequences of two mitochondrial genes (COI and COII) and two nuclear genes (H3 and 28S) from 130 Heliozelidae specimens, including eight of the twelve known genera: Antispila, Antispilina, Coptodisca, Heliozela, Holocacista, Hoplophanes, Pseliastis, and Tyriozela. Our results provide strong support for five major Heliozelidae clades: (i) a large widespread clade containing the leaf-mining genera Antispilina, Coptodisca and Holocacista and some species of Antispila, (ii) a clade containing most of the described Antispila, (iii) a clade containing the leaf-mining genus Heliozela and the monotypic genus Tyriozela, (iv) an Australian clade containing Pseliastis and (v) an Australian clade containing Hoplophanes. Each clade includes several new species and potentially new genera. Collectively, our data uncover a rich and undescribed diversity that appears to be especially prevalent in Australia. Our work highlights the need for a major taxonomic revision of the family and for generating a robust molecular phylogeny using multi-gene approaches in order to resolve the relationships among clades.