Honeybees have been shown to exhibit cognitive performances that were thought to be specific to some vertebrates. However, the molecular and cellular mechanisms of such cognitive abilities of the bees have not been understood. We have identified a novel gene, Mahya, expressed in the brain of the honeybee, Apis mellifera, and other Hymenoptera. Mahya orthologues are present in Deuterostomes but are absent or highly diverged in nematodes and, intriguingly, in two dipteran insects (fruit fly and mosquito) and Lepidoptera (silk moth). Mahya genes encode novel secretory proteins with a follistatin-like domain (Kazal-type serine/threonine protease inhibitor domain and EF-hand calcium-binding domain), two immunoglobulin domains, and a C-terminal novel domain. Honeybee Mahya is expressed in the mushroom bodies and antennal lobes of the brain. Zebra fish Mahya orthologues are expressed in the olfactory bulb, telencephalon, habenula, optic tectum, and cerebellum of the brain. Mouse Mahya orthologues are expressed in the olfactory bulb, hippocampus, and cerebellum of the brain. These results suggest that Mahya may be involved in learning and memory and in processing of sensory information in Hymenoptera and vertebrates. Furthermore, the limited existence of Mahya in the genomes of Hymenoptera and Deuterostomes supports the hypothesis that the genes typically represented by Mahya were lost or highly diverged during the evolution of the central nervous system of specific Bilaterian branches under the specific selection and subsequent adaptation associated with different ecologies and life histories.