New Zealand (NZ) has long been upheld as the archetypical example of a land where the biota evolved without nonvolant terrestrial mammals. Their absence before human arrival is mysterious, because NZ was still attached to East Antarctica in the Early Cretaceous when a variety of terrestrial mammals occupied the adjacent Australian portion of Gondwana. Here we report discovery of a nonvolant mammal from Miocene (19-16 Ma) sediments of the Manuherikia Group near St Bathans (SB) in Central Otago, South Island, NZ. A partial relatively plesiomorphic femur and two autapomorphically specialized partial mandibles represent at least one mouse-sized mammal of unknown relationships. The material implies the existence of one or more ghost lineages, at least one of which (based on the relatively plesiomorphic partial femur) spanned the Middle Miocene to at least the Early Cretaceous, probably before the time of divergence of marsupials and placentals > 125 Ma. Its presence in NZ in the Middle Miocene and apparent absence from Australia and other adjacent landmasses at this time appear to reflect a Gondwanan vicariant event and imply persistence of emergent land during the Oligocene marine transgression of NZ. Nonvolant terrestrial mammals disappeared from NZ some time since the Middle Miocene, possibly because of late Neogene climatic cooling.