The cephalopods have a long geological history, with the first nautiloids found in late Cambrian strata, and purported stem-group representatives present in the earliest Cambrian lagerstätten.
The class developed during the middle Cambrian, and underwent pulses of diversification during the Ordovician period to become diverse and dominant in the Paleozoic and Mesozoic seas. Small shelly fossils such as Tommotia were once interpreted as early cephalopods, but today these tiny fossils are recognized as sclerites of larger animals, and the earliest accepted cephalopods date to the Middle Cambrian Period. During the Cambrian, cephalopods are most common in shallow near-shore environments, but they have been found in deeper waters too. Cephalopods were thought to have "undoubtedly" arisen from within the tryblidiid monoplacophoran clade. However genetic studies suggest that they are more basal, forming a sister group to the Scaphopoda but otherwise basal to all other major mollusc classes. The internal phylogeny of Mollusca, however, is wide open to interpretation – see mollusc phylogeny.
The cephalopods were once thought to have evolved from a monoplacophoran-like ancestor with a curved, tapering shell, and to be closely related to the gastropods (snails). The similarity of the early shelled cephalopod Plectronoceras to some gastropods was used to support this view. The development of a siphuncle would have allowed the shells of these early forms to become gas-filled (thus buoyant) in order to support them and keep the shells upright while the animal crawled along the floor, and separated the true cephalopods from putative ancestors such as , which lacked a siphuncle. Negative buoyancy (i.e. the ability to float) would have come later, followed by swimming in the Plectronocerida and eventually jet propulsion in more derived cephalopods. However, because chambered shells are found in a range of molluscs – monoplacophorans and gastropods as well as cephalopods – a siphuncle is essential to ally a fossil shell conclusively to the cephalopoda. Chambered gastropods can be distinguished from cephalopod shells by the absence of a siphuncle, the irregular spacing of septa, the layering of the shell and (in younger or unmetamorphosed rocks) its microstructure, and the relatively thick width of the shell. The earliest such shells do not have the muscle scars which would be expected if they truly had a monoplacophoran affinity. Additionally, the discovery that , which did not have a shell and appeared to possess jet propulsion in the manner of "derived" cephalopods, complicated the question of the order in which cephalopod features developed – provided it is in fact a cephalopod and not an arthropod.