A variety of social insects use visual cues for homing. In this study, we examine the possible factors affecting the learning and retention of nest-associated visual cues by the Australian desert ant Melophorus bagoti and the manner in which such cues are encoded by foraging ants. We placed four prominent cylindrical landmarks around a nest and trained foragers from that nest to a food source. Ants were tested with the landmark array in a distant testing field after (1) a known number of exposures to the landmarks (1, 3, 7 or 15 trials, spread over a period of 1 day, 2 days or ≥3 days) and (2) after a known period of delay (0, 24, 48, 96 or 192 h). The results show that a combination of an increase in training trials and an increase in number of training days affected the acquisition of landmark memory. Moreover, once the landmarks were learnt, they became a part of long-term memory and lasted throughout the ants’ foraging lifetime. To examine visual cue encoding behaviour, ants trained under similar conditions for 4 days were tested with (1) an identical landmark array, (2) landmarks of the same size used in training, but placed at twice the distance from each other, and (3) landmarks whose dimensions were doubled and placed at twice the distance from each other. In conditions (1) and (3), the ants searched extensively at the centre of the four landmarks, suggesting that, similar to the Saharan ant (genus Cataglyphis) and the honeybee, M. bagoti too uses a snapshot to match the view of the landmarks around the nest. But contrary to the snapshot model, in condition (2), the ants did not search extensively at the centre of the landmarks, but searched primarily 0.5 m from the landmark, the distance from each landmark to the nest during training. We discuss how various search models fare in accounting for these findings.