Two types of fossil Terminalia (Combretaceae) fruits are described from warmer periods in New Zealand's past. One is represented by large “fin-winged” fruit (samara) from the Early Miocene Manuherikia Group sediments of Bannockburn and the Nevis Valley. The form and size of the fruits are entirely unknown in New Zealand today, but strongly resemble those of the genus Terminalia with which they are identified. The second are numerous fruits from the Late Pliocene drift deposit of Weymouth, Manukau Harbour. These are identified with the common drift-fruit, Terminalia catappa, the “sea almond”. The presence of Terminalia in the Miocene and Pliocene of New Zealand is consistent with warmer conditions at those times. The later extinction of the genus meant the loss of the Combretaceae from New Zealand, which is not in the current flora. Based on the current climatic range of other Terminalia around the world, and most Combretaceae, the extinction and continuing absence are probably linked to cold climate conditions.