The authors examine the possibility that Russula prolifica, a commercially important edible mushroom associated with exotic Eucalyptus on the Central Plateau of Madagascar, is a recent introduction from Australia. The new Australian species, described here as R. discolor sp. nov., closely resembles R. prolifica and associates with eucalypts in south-western Australia. While R. prolifica has previously been placed in subsect. Virescentinae of subgen. Heterophyllidiae, this Australian look-alike is not a member of Virescentinae, but belongs in the crown clade of R. subgen. Russula, more precisely in the R. wielangtae lineage of subsect. Auratinae. This paper further provides a detailed type study for R. atroviridis from New Zealand, another presumed member of the R. wielangtae-lineage. However, we show that the current concept of R. atroviridis does not conform to the type specimen which clearly belongs in subsect. Tricholomopsidum of subgen. Russula. The sequences previously deposited in GenBank under the name R. atroviridis represent a different and new species that is here described as R. cooperiana sp. nov. We distinguish two morphologically and genetically different varieties of this species: the type variety associates with Nothofagaceae, while the new var. myrtacearum associates with Myrtaceae. Other potential members of the R. wielangtae lineage are also discussed, including the Australian R. wollumbina. The wider circumscription of subsect. Auratinae is here further supported and its various lineages discussed.