Abstract Evolution is often considered a gradual hill-climbing process, slowly increasing the fitness of organisms. Here I investigate evolution of homing behaviour in simulated intertidal limpets. While the simulation of homing is only a possible mechanism by which homing may have evolved, the process allows an investigation of how evolution may occur over different fitness landscapes. With some fitness landscapes, in order to evolve path integration as a homing mechanism, a temporary reduction in an organism’s fitness was required — since high developmental costs occurred before successful homing strategies evolved. Simple hill-climbing algorithms, therefore, only rarely resulted in the evolution of a functional homing behaviour. The inclusion of trail-following greatly increases the frequency of success of evolution of a path integration strategy. Initially an emergent homing behaviour is formed combining path integration with trail-following. This also demonstrates evolution through exaptation, since in the simulation, the original role of trail-following is likely to be unrelated to homing. Analysis of the fitness landscapes of homing in the presence of trail-following behaviour shows a high variability of fitness, which results in the formation of ‘stepping-stones’ of high fitness across fitness valleys. By using these stepping-stones, simple hill-climbing algorithms can reach the global maximum fitness value.