The position of the earliest-derived living molluscs, the Polyplacophora (chitons) and shell-less vermiform Aplacophora, remains highly contentious despite many morphological, developmental and molecular studies of extant organisms. These two groups are thought to represent either a basal molluscan grade or a clade (Aculifera) sister to the 'higher' molluscs (Conchifera). These incompatible hypotheses result in very different predictions about the earliest molluscs. A new cladistic analysis incorporating both Palaeozoic and extant molluscs is presented here. Our results support the monophyly of Aculifera and suggest that extant aplacophorans and polyplacophorans both derive from a disparate group of multivalved molluscs in two major clades. Reanalysis of the critical Ordovician taxon 'Helminthochiton' thraivensis shows that this animal lacks a true foot despite bearing polyplacophoran-like valves. Its position within our phylogenetic reconstruction indicates that many fossil 'polyplacophorans' in the order Palaeoloricata are likely to represent footless stem-group aplacophorans. 'H.' thraivensis and similar forms such as Acaenoplax may be morphological stepping stones between chitons and the shell-less aplacophorans. Our results imply that crown-group molluscan synapomorphies include serial repetition, the presence of a foot, a mineralized scleritome and a creeping rather than worm-like mode of life.