Tree hollows are a critical, yet potentially limiting habitat resource for many animal species. Fire influences hollow availability, and the associated indirect effects on fauna can threaten the persistence of hollow-dependent species in fire-prone systems. We investigated the influence of two temporal aspects of fire regimes (time-since-fire, inter-fire interval) on hollow occurrence in a semi-arid, fire-prone region in south-eastern Australia. Empirical data on the characteristics of hollow-bearing eucalypt stems and fire-history attributes were compiled for 581 study sites. Mixed models were used to examine the relative influence of time-since-fire and inter-fire interval on hollow occurrence. Time-since-fire and inter-fire interval both affected the probability of hollow occurrence, but in different ways. Time-since-fire influenced the occurrence of hollows in live and dead stems. As time-since-fire increased, so too did the probability of live and dead stems containing hollows. Live stems did not provide hollows before 40years post-fire, while the probability of dead stems containing hollows peaked at 50–60years. Inter-fire interval influenced the availability of hollows in dead stems. Longer inter-fire intervals resulted in an increased density of dead hollow-bearing stems. In this region, hollow-dependent fauna will benefit from increased fire-free periods, both in terms of individual fire events and the intervals between repeated fires. These results highlight the complex way in which fire affects the availability of faunal habitat resources, and the extended time periods over which such influences operate. Understanding the effects of fire regimes on slow-developing habitat resources over long time-frames is imperative for sound ecological fire management.