The Hymenoptera show a high propensity for transitions from arrhenotokous reproduction (diploid females develop from fertilized eggs, haploid males from unfertilized eggs) to thelytokous reproduction (diploid females develop from unfertilized eggs). However, the evolution of thelytoky is frequently constrained by the sex determination system. Under the ancestral system, complementary sex determination (CSD), the constraint results from the production of diploid males by thelytokous females. The magnitude of this constraint depends on the cytological mechanism of thelytoky, determining the rate at which thelytokous lines lose heterozygosity and on whether a single locus or multiple loci are involved in CSD. In this review, it is discussed how diploid male production in the case of CSD or other constraints in the case of alternative sex determination systems may impede transitions to thelytoky, but it is also shown that under particular (and presumably rare) circumstances the production of diploid males will promote rather than hamper the evolution of thelytoky. Furthermore, constraints between the evolution of thelytoky and sex determination may be mutual, because once thelytoky has evolved, it can impact on sex determination. Finally, researchers are encouraged to exploit the frequent occurrence of thelytoky as an opportunity to learn more about the mechanisms of sex determination in the Hymenoptera.