Here, we aimed at estimating sex-specific heritabilities of cell-mediated immune response (CMI) in the blue tit nestlings (Cyanistes caeruleus). To separate genetic and environmental components of the phenotypic variance in CMI (measured using phytohaemagglutinin assay), we performed a cross-fostering experiment. Additionally, controlled environmental variation was introduced by enlarging some broods. Our analyses revealed a significant genetic component (as approximated by the nest-of-origin term) of the phenotypic variance in immune response. More importantly, these genetic effects differed between sexes and experimentally manipulated brood sizes, as indicated by significant genotype-by-sex and genotype-by-environment interactions. We discuss possible causes of such sexual dimorphism in gene expression and suggest that sex- and environment-specific genetic interactions may contribute to the maintenance of genetic variability in traits related to immune functions.