Eucryphia leaves recovered from Tertiary sediments in south-eastern Australia are assigned to three new species, E. falcata (Late Palaeocene, Lake Bungarby), E. microstoma (Early Eocene, Regatta Point) and E. aberensis (Middle to Late Eocene, Loch Aber). Leaves from Early Pleistocene sediments at Regatta Point are re-examined and are considered to be closely related to the extant species, E. lucida and E. milliganii. An examination of the leaf morphology of the fossil and extant species suggests that evolution has taken place, resulting in smaller leaves at higher latitudes and/or altitudes probably in response to climatic change. There is also evidence for an increase in the size and complexity of peltiform cuticular extensions on the abaxial leaf surface from the Early Tertiary to the present, which may be a response to lower water availability or increasing occurrence of frost.