Animals are capable of true navigation if, after displacement to a location where they have never been, they can determine their position relative to a goal without relying on familiar surroundings, cues that emanate from the destination, or information collected during the outward journey. So far, only a few animals, all vertebrates, have been shown to possess true navigation. Those few invertebrates that have been carefully studied return to target areas using path integration, landmark recognition, compass orientation and other mechanisms that cannot compensate for displacements into unfamiliar territory. Here we report, however, that the spiny lobster Panulirus argus oriented reliably towards a capture site when displaced 12–37 km to unfamiliar locations, even when deprived of all known orientation cues en route. Little is known about how lobsters and other animals determine position during true navigation. To test the hypothesis that lobsters derive positional information from the Earth's magnetic field, lobsters were exposed to fields replicating those that exist at specific locations in their environment. Lobsters tested in a field north of the capture site oriented themselves southwards, whereas those tested in a field south of the capture site oriented themselves northwards. These results imply that true navigation in spiny lobsters, and perhaps in other animals, is based on a magnetic map sense.