Traits under relaxed selection are expected to become reduced or disappear completely, a process called vestigialization. In parthenogenetic populations, traits historically involved in sexual reproduction are no longer under selection and potentially subject to such reduction. In Leptopilina clavipes, thelytokous (parthenogenetic) populations are infected by Wolbachia bacteria. Arrhenotokous populations do not harbor Wolbachia. When antibiotics are applied to infected females, they are cured from their infection and males arise. Such males are capable of producing offspring with uninfected females, but with lower fertilization success than sexual males. This can be attributed to the lack of selection on male fertility in thelytokous lines. In this study we used this variation in L. clavipes male fertility to determine the genetic basis of this trait. Males from cured thelytokous populations were crossed to females from uninfected populations. Using AFLP markers, a genetic linkage map was generated, consisting of five linkage groups and spanning a total distance of 219.9 cM. A single QTL of large effect (explaining 46.5% of the phenotypic variance) was identified for male fertility, which we call male fertility factor (mff). We discuss possible mechanisms underlying the effect of mff, as well as mechanisms involved in vestigialization of traits involved in sexual reproduction.