Fossils from the Newvale lignite mine, Southland, are the first substantiated foliar records of Proteaceae subfamily Persoonioideae. The fossils possess very large stomata, a probable synapomorphy for Persoonioideae, and within Proteaceae the combination of this feature and more or less parallel-aligned, brachyparacytic stomatal complexes and undulate anticlinal epidermal cell walls is uniquely found in this subfamily. The new genus Persoonieaephyllum is described to recognise affinity of the fossil leaves and cuticles with tribe Persoonieae of Persoonioideae and their distinction from its only other extant representative, Placospermum. Two new species are described. P. ornatum is represented by linear leaves less than 20 mm wide and possessing more or less parallel-aligned major veins. These leaves closely match those of extant hypostomatic, broad-leaved species of tribe Persoonieae and are distinct from Placospermum in venation and several cuticular details. P. villosum has so far been recovered only as cuticular material in disaggregated lignite. It is distinct from P. ornatum in having abundant trichome bases, an absence of surface tubercules, and even larger stomata (guard cells often >70 μm long). The fossils extend the known record of Persoonioideae in the New Zealand–New Caledonia region by ~20 million years.