Eucalyptus virginea and E. relicta are described from Mt Lindesay National Park and from the Whicher Range south-east of Busselton respectively. Both species, together with E. lane-poolei, are in the earliest branching clade of E. ser. Curviptera, which contains many horticulturally attractive large-flowered mallees from semi-arid and desert regions such as E. macrocarpa and E. youngiana. The discovery and description of these two rare relictual forest trees so recently highlights the need for ongoing botanical survey of south-western Australia’s forests. A phantom hybrid, Eucalyptus lane-poolei × relicta, is also described for the first time. It occurs close to populations of E. relicta in the Whicher Range but 150 km south of the nearest recorded E. lane-poolei.