Around 540 million years ago there was a sudden, dramatic adaptive radiation known as the Cambrian Explosion. This event marked the origin of almost all of the phyla (major lineages characterized by fundamental body plans) of animals that would ever live on earth, as well the appearance of many notable features such as rigid skeletons and other hard parts, complex jointed appendages, eyes, and brains. This radical evolutionary event has been a major puzzle for evolutionary biologists since Darwin, and while our understanding of it has recently improved with new fossil finds, richer molecular phylogenies, and better grasp of ecological, evolutionary, and developmental processes generally, unanswered questions remain. In this paper I argue that a basic cognitive toolkit for embodied, object-oriented, spatial cognition (what I call Basic Cognitive Embodiment) is a practical necessity for control of a large, mobile, complexly articulated body in space. This hypothesis allows us to relate the complexification of animal bodies to the complexification of perception, cognition and behavior in a way that can help to fill in gaps in our emerging picture of the Cambrian Explosion, as well as shed light on the deep evolutionary origins of the mind.