The first record of the flamingo-like Palaelodidae (Phoenicopteriformes) is reported from the Early Miocene, St Bathans Fauna of Central Otago, New Zealand. Two distal tibiotarsi are described as a new Palaelodus species and a cranial fragment of a sternum is tentatively assigned to the same taxon. The new species is slightly smaller than P. wits:mu from the Late Oligocene-Early Miocene of Australia, and is distinguished from all congeners by a more robust shaft with a gradual expansion of width to the distal condyles.