Nautiloids are descendents of a diverse group of shelled animals that lived in every ocean on Earth. Only a few species are living today (extant) around Australia and the Philippines. They first appeared more than 500 million years ago, during the Cambrian, and had simple cone-shaped shells. The next 50 million years saw a huge diversification of nautiloids into several thousand species. One group of nautiloids had coiled shells, ancestors to the coiled Nautilus we see today. Fossil evidence suggests that during the Ordovician, they were the main predators in the sea, feeding on small, ocean-bottom animals. During an ice age about 450 million years ago, many species of nautiloids became extinct, but the coiled ones were among the survivors. During the Devonian, more extinctions occurred, perhaps related to the rise of bony fishes and sharks. Because nautiloids were slow-moving, fishes and sharks could beat them to their prey.

Compared to modern cephalopods, the fossil record reveals 20 times the number of species. The first cephalopods appeared during the late Cambrian (about 500 million years ago). They looked like squid, but with long, cone-shaped shells from which they extended their tentacles. Typically, the shells were divided into chambers (septa), added on as the animal grew. Some early cephalopods were enormous, as long as a school bus. For animals without backbones (invertebrates), they were sophisticated, with nervous systems and the ability to swim by jet propulsion. By the end of the Paleozoic (250 million years ago), cephalopods had diversified to include coiled shells like a modern nautilus. While the extinction event at the end of the Paleozoic impacted many species, cephalopods flourished again during the Triassic and Jurassic. The extinction event at the end of the Cretaceous (65 million years ago) left only the nautiloids and the coleoids (octopus and squid).