Many species modify their behaviour in response to the scents of their predators, but species or populations living without predators may lose such abilities. This loss has been suggested to be irreversible, and to constitute a significant hurdle in restoring historical ecosystems. Olfactory predator recognition was studied in two macropodid marsupials - the tammar wallaby (Macropus eugenii) and the red-necked pademelon (Thylogale thetis). Both species are in the ‘critical weight range’ of Australian native mammals that have been negatively affected by the introduction of novel predators since European settlement. Predator-naïve animals were tested by exposing subjects simultaneously to two feeders with either a predator or a herbivore faecal or urine sample beneath the food tray. The presence of predator olfactory cues beneath the feeder did not affect foraging behaviour or feeder use when compared to control stimuli (herbivore faeces or urine). Previous studies have found that predator-experienced herbivorous marsupials modify their behaviour in the presence of predator scents. In contrast, our studies of predator-naïve individuals found no evidence of such selectivity, suggesting that marsupial herbivores may have to learn to modify their behaviour in response to olfactory cues from predators. This implies that the loss of olfactory predator recognition may not be irreversible. Animals translocated from predator-free areas could potentially be trained to recognise the smells of their predators.