Cephalopods are extraordinary molluscs equipped with vertebrate-like intelligence and a unique buoyancy system for locomotion. A growing body of evidence from the fossil record, embryology and Bayesian molecular divergence estimations provides a comprehensive picture of their origins and evolution. Cephalopods evolved during the Cambrian (∼530 Ma) from a monoplacophoran-like mollusc in which the conical, external shell was modified into a chambered buoyancy apparatus. During the mid-Palaeozoic (∼416 Ma) cephalopods diverged into nautiloids and the presently dominant coleoids. Coleoids (i.e. squids, cuttlefish and octopods) internalised their shells and, in the late Palaeozoic (∼276 Ma), diverged into Vampyropoda and the Decabrachia. This shell internalisation appears to be a unique evolutionary event. In contrast, the loss of a mineralised shell has occurred several times in distinct coleoid lineages. The general tendency of shell reduction reflects a trend towards active modes of life and much more complex behaviour.