Previous studies demonstrate that soft-bodied (coleoid) cephalopods are adept at learning and remembering features of their environment, but little is known about their primitive relative, nautilus. Nautilus makes nightly migrations from deep to shallow water along coral reef slopes, covering large areas of varied substrate. Memory of its surroundings may be advantageous, but the nautilus brain is the simplest among extant cephalopods, lacking dedicated neural regions that support learning and memory in other cephalopods. The authors hypothesize that the absence of these regions in nautilus may affect memory storage. Here the authors report the first evidence for spatial memory in 2- and 3-dimensional arenas. In a small open-field maze, nautiluses learned the location of a goal within 3 trials, and memory was stable for at least 2 weeks. In 3-dimensional environments, animals habituated within and across trials when their surroundings were unchanged, but activity increased when the environment changed topographically, although not when the change was visual only. These results are comparable to performances of coleoids in similar tasks and are surprising given the far simpler neuroanatomy of nautilus.