In insect brains, the mushroom bodies (MBs) are a higher-order center for sensory integration and memory. Honeybee (Apis mellifera L.) MBs comprise four Kenyon cell (KC) subtypes: class I large-, middle-, and small-type, and class II KCs, which are distinguished by the size and location of somata, and gene expression profiles. Although these subtypes have only been reported in the honeybee, the time of their acquisition during evolution remains unknown. Here we performed in situ hybridization of tachykinin-related peptide, which is differentially expressed among KC subtypes in the honeybee MBs, in four hymenopteran species to analyze whether the complexity of KC subtypes is associated with their behavioral traits. Three class I KC subtypes were detected in the MBs of the eusocial hornet Vespa mandarinia and the nidificating scoliid wasp Campsomeris prismatica, like in A. mellifera, whereas only two class I KC subtypes were detected in the parasitic wasp Ascogaster reticulata. In contrast, we were unable to detect class I KC subtype in the primitive and phytophagous sawfly Arge similis. Our findings suggest that the number of class I KC subtypes increased at least twice - first with the evolution of the parasitic lifestyle and then with the evolution of nidification.