The desert ant, Cataglyphis fortis, uses both visual and olfactory cues to guide its return to the nest. The ants use vision-based path integration for long-distance navigation and memorize the visual and olfactory surrounding of the nest to finally locate the entrance. In the present study we investigated how the visual and the olfactory navigation systems interact. In field experiments ants were trained to associate the nest with a visual cue, an olfactory cue or a combination of both cues. We tested ants after one, five and 15 training runs, to investigate whether the ants would make use of the training cues to pinpoint the nest. We found that they were slow to learn the location of the nest when it was specified by just an olfactory or a visual cue. However, the ants focused their nest search after the first training run with the combined cue. Equally experienced ants responded to the individually presented visual or olfactory cues with the same high accuracy as they did to the combined cue. After 15 training runs, the combined cue still evoked an accurate response in the test, whereas the individually presented cues no longer did. Apparently, C. fortis benefit from combining their visual and olfactory navigational tools, because the bimodal sensory input accelerates the acquisition of landmark information.