Background. New Zealand's lesser short-tailed bat Mystacina tuberculata is one of only two of c.1100 extant bat species to use a true walking gait when manoeuvring on the ground (the other being the American common vampire bat Desmodus rotundus). Mystacina tuberculata is also the last surviving member of Mystacinidae, the only mammalian family endemic to New Zealand (NZ) and a member of the Gondwanan bat superfamily Noctilionoidea. The capacity for true quadrupedal terrestrial locomotion in Mystacina is a secondarily derived condition, reflected in numerous skeletal and muscular specializations absent in other extant bats. The lack of ground-based predatory native NZ mammals has been assumed to have facilitated the evolution of terrestrial locomotion and the unique burrowing behaviour of Mystacina, just as flightlessness has arisen independently many times in island birds. New postcranial remains of an early Miocene mystacinid from continental Australia, Icarops aenae, offer an opportunity to test this hypothesis. Results. Several distinctive derived features of the distal humerus are shared by the extant Mystacina tuberculata and the early Miocene Australian mystacinid Icarops aenae. Study of the myology of M. tuberculata indicates that these features are functionally correlated with terrestrial locomotion in this bat. Their presence in I. aenae suggests that this extinct mystacinid was also adapted for terrestrial locomotion, despite the existence of numerous ground-based mammalian predators in Australia during the early Miocene. Thus, it appears that mystacinids were already terrestrially-adapted prior to their isolation in NZ. In combination with recent molecular divergence dates, the new postcranial material of I. aenae constrains the timing of the evolution of terrestrial locomotion in mystacinids to between 51 and 26 million years ago (Ma). Conclusion. Contrary to existing hypotheses, our data suggest that bats are not overwhelmingly absent from the ground because of competition from, or predation by, other mammals. Rather, selective advantage appears to be the primary evolutionary driving force behind habitual terrestriality in the rare bats that walk. Unlike for birds, there is currently no evidence that any bat has evolved a reduced capacity for flight as a result of isolation on islands.