The current study presents the most detailed multigene phylogenetic assessment of the red algal family Kallymeniaceae to date emphasising the floras of Australia (220 specimens), Europe (19 specimens) and North America (54 specimens). Toward a natural classification and in light of our phylogenetic results, we propose numerous taxonomic changes including the recognition of ten new genera: Austrokallymenia Huisman & G.W.Saunders; Glaphyrymeniopsis Kraft & G.W.Saunders; Huonia G.W.Saunders; Leiomenia Huisman & G.W.Saunders; Metacallophyllis A.Vergés & L.Le Gall; Nothokallymenia A.Vergés & L.Le Gall; Rhipidomenia G.W.Saunders; Thalassiodianthus G.W.Saunders & Kraft; Tytthomenia G.W.Saunders; and Verlaquea L.Le Gall & A.Vergés. The proposals of new genera are accompanied by 16 new combinations of which half are for species from the formerly species-rich genus Kallymenia. Approximately 50 undescribed genetic species were uncovered, of which only ten are now formally named, five of which are type species for new genera: Glaphyrymeniopsis mollis Kraft & G.W.Saunders, Huonia sandersonii G.W.Saunders, Leiomenia lacunata Huisman & G.W.Saunders, Thalassiodianthus incrassatus G.W.Saunders & Kraft and Tytthomenia barrettii G.W.Saunders. The remaining five are Austrokallymenia rebeccae G.W.Saunders & Kraft, A. roensis Huisman & G.W.Saunders, Leiomenia imbricata Huisman & G.W.Saunders, Meredithia compaginata G.W.Saunders, and Verlaquea fimbriata G.W.Saunders. Also described and illustrated for the first time are reproductive features of the northeastern-Pacific Euthora timburtonii Clarkston & G.W.Saunders, which has been known until now only from molecular studies of vegetative thalli. Despite advances made by our work, the need for considerably more taxonomic investigation in this diverse family is demonstrated, particularly within the presently constituted genus Callophyllis.