Australian desert ants, Melophorus bagoti, return home after foraging by means of path integration and visual navigation. If these mechanisms do not deliver them exactly at the inconspicuous nest entrance, they engage in a systematic search. Here we describe the structure of this search pattern in detail. Trained ants ran home from a feeder in the natural visual setting where they navigated very accurately, and were then captured for tests on a distant test field after they had almost reached their nest. The search pattern consisted of loops and was centred on the position where the nest was most likely to be located. At first, it covered a rather small area, but then gradually extended outwards to cover a larger area. The search density was also adapted to the preceding outbound foraging distance, with longer distances leading to flatter, wider search distributions. Since the visual surround at the time of capture was similar for ants with all outbound distances, we suggest this is an adaptation to the cumulative error of the homing vector. The frequency distribution of segment lengths in the paths of searching ants does not show characteristics of a Lévy walk strategy. Instead, it is well described by a double exponential model, lending support to a theoretically optimal strategy that consists of a mixture of two random walks, as in the composite Brownian walk strategy.