In Tribolium flour beetles and other organisms, individuals migrate between heterogeneous environments where they often encounter markedly different nutritional conditions. Under these circumstances, theory suggests that genotype-by-environment interactions (GEI) may be important in facilitating adaptation to new environments and maintaining genetic variation for male traits subject to directional selection. Here, we used a nested half-sib breeding design with Tribolium castaneum to partition the separate and joint effects of male genotype and nutritional environment on phenotypic variation in a comprehensive suite of life-history traits, reproductive performance measures across three sequential sexual selection episodes, and fitness. When male genotypes were tested across three nutritional environments, considerable phenotypic plasticity was found for male mating and insemination success, longevity and traits related to larval development. Our results also revealed significant additive genetic variation for male mating rate, sperm offence ability (P2), longevity and total fitness and for several traits reflecting both larval and adult resource use. In addition, we found evidence supporting GEI for sperm defence ability (P1), adult longevity and larval development; thus, no single male genotype outperforms others in every nutritional environment. These results provide insight into the potential roles of phenotypic plasticity and GEI in facilitating Tribolium adaptation to new environments in ecological and evolutionary time.