104We study learning in the ancient cephalopod Nautilus pompilius as a way of understanding how behavioral and neural complexity may have evolved in its more derived relatives, the coleoid cephalopods (octopuses, cuttlefish, and squid), whose brains are heavily invested in learning and memory. Nautilus retains a relatively primitive brain whereas coleoid brains are among the most complex of all the invertebrates, containing several discrete lobes dedicated to learning and memory storage—the vertical and frontal lobe complexes. The nautilus CNS lacks known homologues or analogues of these regions, and instead the brain more likely approximates those of the ancestors of the two extant subclasses. Nautilus is therefore uniquely placed in this lineage for studies of the evolution of complex behavior, including learning and memory. We identify and characterize learning, memory formation, composition, and retrieval in Nautilus through controlled classical conditioning studies and also behavioral assays with free-moving animals. In studies of classical conditioning where a light predicted the reward of food, nautiluses learned rapidly, expressing temporally separated short-term and long-term memory (STM and LTM). STM expression in Nautilus was similar to results from coleoids, but LTM was of shorter duration, perhaps due the lack of dedicated learning and memory centers found in more derived cephalopods. Spatial memory studies in complex mazes have revealed far more complex information processing than the “primitive brain” of nautiluses might predict. By providing increasingly complex cue arrays to be learned for spatial navigation to a goal, we investigated how nautiluses perform in complex cognitive tasks similar to those tested in coleoids. Nautiluses were trained to escape from a shallow-water, brightly lit arena (aversive) into deep, dark water (reward) via a hole in the arena—with the aid of either a beacon proximate to the goal or multiple visual cues in the arena located proximate and distant from the escape point. We found evidence for rapid learning, memory of long duration, and dynamic switching among learned navigational tactics when the cue arrays were altered. Current studies focusing on what information is retained, processed, and used to navigate reveal that nautiluses can simultaneously learn and remember net displacement (dead reckoning of turns and distance traveled) and beacon information (both associative and spatial) proximate to the escape point as they navigate toward the goal location.