The New Zealand endemic bat family Mystacinidae comprises just two Recent species referred to a single genus, Mystacina. The family was once more diverse and widespread, with an additional six extinct taxa recorded from Australia and New Zealand. Here, a new mystacinid is described from the early Miocene (19-16 Ma) St Bathans Fauna of Central Otago, South Island, New Zealand. It is the first pre-Pleistocene record of the modern genus and it extends the evolutionary history of Mystacina back at least 16 million years. Extant Mystacina species occupy old-growth rainforest and are semi-terrestrial with an exceptionally broad omnivorous diet. The majority of the plants inhabited, pollinated, dispersed or eaten by modern Mystacina were well-established in southern New Zealand in the early Miocene, based on the fossil record from sites at or near where the bat fossils are found. Similarly, many of the arthropod prey of living Mystacina are recorded as fossils in the same area. Although none of the Miocene plant and arthropod species is extant, most are closely related to modern taxa, demonstrating potentially long-standing ecological associations with Mystacina.