A new genus and species of fossil bat is described from New Zealand's only pre-Pleistocene Cenozoic terrestrial fauna, the early Miocene St Bathans Fauna of Central Otago, South Island. Bayesian total evidence phylogenetic analysis places this new Southern Hemisphere taxon among the burrowing bats (mystacinids) of New Zealand and Australia, although its lower dentition also resembles Africa's endemic sucker-footed bats (myzopodids). As the first new bat genus to be added to New Zealand's fauna in more than 150 years, it provides new insight into the original diversity of chiropterans in Australasia. It also underscores the significant decline in morphological diversity that has taken place in the highly distinctive, semi-terrestrial bat family Mystacinidae since the Miocene. This bat was relatively large, with an estimated body mass of ~40 g, and its dentition suggests it had an omnivorous diet. Its striking dental autapomorphies, including development of a large hypocone, signal a shift of diet compared with other mystacinids, and may provide evidence of an adaptive radiation in feeding strategy in this group of noctilionoid bats.