Prerequisite for tracing nervous system evolution is understanding of the body plan, feeding behaviour and locomotion of the first animals in which neurons evolved. Here, a comprehensive scenario is presented for the diversification of cell types in early metazoans, which enhanced feeding efficiency and led to the emergence of larger animals that were able to move. Starting from cup-shaped, gastraea-like animals with outer and inner choanoflagellate-like cells, two major innovations are discussed that set the stage for nervous system evolution. First, the invention of a mucociliary sole entailed a switch from intra- to extracellular digestion and increased the concentration of nutrients flowing into the gastric cavity. In these animals, an initial nerve net may have evolved via division of labour from mechanosensory-contractile cells in the lateral body wall, enabling coordinated movement of the growing body that involved both mucociliary creeping and changes of body shape. Second, the inner surface of the animals folded into metameric series of gastric pouches, which optimized nutrient resorption and allowed larger body sizes. The concomitant acquisition of bilateral symmetry may have allowed more directed locomotion and, with more demanding coordinative tasks, triggered the evolution of specialized nervous subsystems. Animals of this organizational state would have resembled Ediacarian fossils such as Dickinsonia and may have been close to the cnidarian-bilaterian ancestor. In the bilaterian lineage, the mucociliary sole was used mostly for creeping, or frequently lost. One possible remnant is the enigmatic Reissner's fibre in the ventral neural tube of cephalochordates and vertebrates.