We examine the complex evolution of animal nervous systems and discuss the ramifications of this complexity for inferring the nature of early animals. Although reconstructing the origins of nervous systems remains a central challenge in biology, and the phenotypic complexity of early animals remains controversial, a compelling picture is emerging. We now know that the nervous system and other key animal innovations contain a large degree of homoplasy, at least on the molecular level. Conflicting hypotheses about early nervous system evolution are due primarily to differences in the interpretation of this homoplasy. We highlight the need for explicit discussion of assumptions and discuss the limitations of current approaches for inferring ancient phenotypic states.