Targeted searches of approximately 150 km of cliff lines for two rare sandstone shrubs, Melaleuca triumphalis Craven and Stenostegia congesta A.R.Bean, thought to be restricted to the Victoria River gorge system within Gregory National Park, increased the number of known populations from 3 and 6 to 31 and 37, respectively. Both species occur predominantly in rocky and often fire-protected niches on sandstone cliffs and scree slopes, and are frequently associated with permanent drip-lines and seepage areas. Although their broad habitat requirements are similar, the two species do occur in slightly different niches. The data presented here suggest that M. triumphalis is reasonably fire tolerant, whereas S. congesta appears to be more fire sensitive. Weeds and introduced animals are not thought to pose a threat to these rare species. Models developed using remotely sensed and landscape-scale data (digital elevation models, radiometrics, geology and distance to rivers and streams) suggest that these species may also occur outside Gregory National Park in other areas of the Northern Territory such as on Bullo River and Bradshaw stations and in Keep River National Park. It is suggested that both species be regarded as Vulnerable under the IUCN guidelines.