Nest boxes are routinely installed as a substitute for natural tree hollows to provide den and nest sites for a range of hollow-utilising fauna. We installed 120 nest boxes in 20 patches of indigenous vegetation (remnants) across the urban/suburban landscape of Melbourne, south-eastern Australia, and investigated their use by indigenous and exotic vertebrate species over a period of 12 months. Nest-box use was dominated by the common brushtail possum (Trichosurus vulpecula), the common ringtail possum (Pseudocheirus peregrinus) and the common myna (Acridotheres tristis), an aggressive introduced bird. We found that brushtail and ringtail possums utilised nest boxes all year round but more frequently in cooler months (May–August). Common mynas dominated nest-box use during spring/summer, potentially reducing the availability of this resource to indigenous species. We found evidence that the probability of a nest box being occupied by either species of possum was greater in remnants with abundant possum populations. Brushtail possums preferred thick-walled pine nest boxes over thin-walled plywood nest boxes, most likely owing to differences in their thermal insulation properties. Although considerable economic costs would be involved in using nest boxes as a long-term substitute for hollow-bearing trees, nest boxes may provide a temporary hollow resource until hollow-bearing trees are recruited in urban remnants.