Among non-human animals, crows, octopuses and honeybees are well-known for their complex brains and cognitive abilities. Widening the lens from the idiosyncratic abilities of exemplars like these to those of animals across the phylogenetic spectrum begins to reveal the ancient evolutionary process by which complex brains and cognition first arose in different lineages. The distribution of 35 phenotypic traits in 17 metazoan lineages reveals that brain and cognitive complexity in only three lineages (vertebrates, cephalopod mollusks, and euarthropods) can be attributed to the pivotal role played by body, sensory, brain and motor traits in active visual sensing and visuomotor skills. Together, these pivotal traits enabled animals to transition from largely reactive to more proactive behaviors, and from slow and two-dimensional motion to more rapid and complex three-dimensional motion. Among pivotal traits, high-resolution eyes and laminated visual regions of the brain stand out because they increased the processing demands on and the computational power of the brain by several orders of magnitude. The independent acquisition of pivotal traits in cognitively complex (CC) lineages can be explained as the completion of several multi-trait transitions over the course of evolutionary history, each resulting in an increasing level of complexity that arises from a distinct combination of traits. Whereas combined pivotal traits represent the highest level of complexity in CC lineages, combined traits at lower levels characterize many non-CC lineages, suggesting that certain body, sensory and brain traits may have been linked (the trait-linkage hypothesis) during the evolution of both CC and non-CC lineages.