Female dung flies Scathophaga stercoraria (L.) store sperm from several males in three or four spermathecae. Selection on the number of spermathecae was successful and the morphological intermediate stages in the evolution from three to four spermathecae are illustrated. The genetic quality of a male from a female’s perspective depends on an interaction between their genotypes and the microhabitat in which the offspring will grow. Females influence the paternity pattern of their offspring, and do this differently in different microhabitats. Females with four spermathecae are better able to influence paternity than are those with three spermathecae. However, there must be a cost to building and maintaining an extra spermatheca. We estimate, using the animal model on pedigree data, that this cost is approximately five eggs per clutch, i.e. around 8% of the mean clutch size. This is a substantial cost and such costs should not be ignored in discussions of the benefits to females of assessing the genetic qualities of their mating partners. We suggest that the number of spermathecae in the study population is stable because the relative benefits in quality of offspring through cryptic female choice is balanced by the costs in total numbers of offspring.