During ecological speciation diverging populations are exposed to contrasting sensory and spatial information that present new behavioral and perceptive challenges. Here, we investigate how brain composition evolves during the early stages of speciation. The incipient species pair, Heliconius erato cyrbia and H. himera, have parapatric ranges across an environmental and altitudinal gradient. Despite continuing gene-flow, these species have divergent ecological, behavioral and physiological traits. We demonstrate that these incipient species also differ significantly in brain composition, especially in the size of sensory structures. H. erato has larger visual components whilst H. himera invests more heavily in olfaction. These differences are not explained by environmentally-induced plasticity, but reflect non-allometric shifts in brain structure. Our results suggest the adaptive evolution of brain structure and function play an important role in facilitating the emergence of ecologically distinct species, and imply that plasticity alone may be insufficient to meet the demands of novel environments.