There has been marked recent decline in the terrestrial mammal fauna across much of northern Australia, with most documentation of such decline for lowland areas. Here we report changes in the assemblage of small mammals in a rugged sandstone environment (Nawurlandja, in Kakadu National Park) over intermittent sampling between 1977 and 2002. Four native mammal species were commonly recorded in the original sampling: sandstone antechinus (Pseudantechinus bilarni), northern quoll (Dasyurus hallucatus), Arnhem rock-rat (Zyzomys maini) and common rock-rat (Z. argurus). Trap success rates declined significantly for the northern quoll, Arnhem rock-rat and all species combined, but increased for the common rock-rat. Despite being recorded commonly in the initial (1977–79) study, no Arnhem rock-rats were recorded in the most recent (2002) sampling. Trap success rates for northern quoll declined by ~90% from 1977–79 to 2002. The reasons for change are not clear-cut. Notably, all sampling occurred before the arrival of cane toads (Rhinella marina), a factor that has caused severe decline in northern quoll numbers elsewhere. Fire was more frequent in the sampling area in the period preceding the 2002 sampling than it was in the period preceding the initial (1977–79) sampling, and this may have contributed to change in mammal abundance.