Mother of all squid!
Well, more like great-great-many-times-great-aunt of all squid, but it's still a spectacular fossil. Behold the Cambrian mollusc, Nectocaris pteryx.
(Click for larger image)
Reconstruction of Nectocaris pteryx.
This was one of those confusing, uninterpretable Cambrian animals, represented by only one poorly preserved specimen. Now, 91 new specimens have been dug up and interpreted, and it makes sense to call it a cephalopod. It has two camera eyes — not arthropod-like compound eyes — on stalks, an axial cavity containing paired gills like the mantles of modern cephalopods, and a flexible siphon opening into that cavity. There are also subtle similarities in the structure of the connective tissue in the lateral fins. Obviously, it has a pair of tentacles; no mouthparts have been preserved, but there are hints in the form of dark deposits between the tentacles, which may be all that's left of the mouthparts — and are in the right place for a cephalopod ancestor.
There are still mysteries. There's no hint of a shell; previous theories had postulated a shelled common ancestor to squid, nautiloids, and ammonoids, but either this was a specialized branch that lost the shell, or modern cephalopod groups independently re-evolved the structure. It also has only two tentacles! Again, we don't know whether this was the ancestral condition, or whether Nectocaris is the product of a derived fusion. Known cephalopod Hox genes use a novel combinatorial scheme to encode arm identities, so I guess I wouldn't be too shocked if the eight- to ten-arm condition is a relatively recent (in geological terms!) innovation.
About that great-aunt remark…here's where their analysis places the Nectocarids, as a Cambrian side-branch of the group that led to the modern forms.
(Click for larger image)
Phylogenetic position of the nectocaridids. Arrows indicate the crown groups of 1, molluscs; 2, conchifera; 3, cephalopods. Stars represent the earliest record of mineralization in each lineage. Clade divergence times (dotted lines) are unconstrained. Early branches follow previous phylogeny.
Note the dotted lines everywhere — those are lineages that we haven't found in the fossil record yet. Nectocaris is small (about 4cm long) and softbodied, and it required excellent preservation for any trace of them to survive. Specimens from the beginning of the Cambrian, representative of the groups indicated by the red arrows at 1 and 2, would be wonderful to have…but they're also going to be forms that wouldn't have been ideal for fossilization. Clearly, we need to fund more paleontology.
Ed Yong has more to say at Not Exactly Rocket Science.
Smith MR, Caron J-B (2010) Primitive soft-bodied cephalopods from the Cambrian. Nature http://dx.doi.org/10.1038/nature09068.