Living ectocochliate cephalopods have long been thought to be restricted to a single genus, Nautilus Linnaeus, 1758, comprising five or six extant species. The shells of two species, N. scrobiculatus Lightfoot, 1786, and N. perforatus Conrad, 1847, are quite distinct, but no soft-parts were known until 1984, when N. scrobiculatus was seen alive for the first time. Dissections show that significant anatomical differences exist between N. scrobiculatus and other Nautilus species, including differences in gill morphology and details of the male reproductive system. These differences, along with phylogenetic analysis of extant and selected fossil nautiloid species, indicate that N. scrobiculatus, and N. perforatus should be distinguished from Nautilus as a newly defined genus, Allonautilus. This analysis contradicts previous phylogenies proposed for the Nautilida, which placed Nautilus as the last-evolved member of the order. We surmise that Allonautilus is a descendent of Nautilus, that the latter is paraphyletic, and first evolved in the Mesozoic, rather than in the late Cenozoic, as has been previously suggested.