Selection of oviposition substrate is critical in holometabolous insects. Female stable flies, Stomoxys calcitrans, locate and select vertebrate herbivore dung in which they lay their eggs. However, the preference for vertebrate herbivore dung by S. calcitrans females, its fitness consequences for offspring, and the semiochemicals used to locate and select oviposition substrates remain unclear. Using oviposition choice tests and life table bioassays we found that gravid female S. calcitrans prefer to oviposit on donkey and sheep dung, which also improves the performance of their offspring. GC-MS analysis followed by random forest classification identified β-citronellene and carvone as the most important predictive volatile organic compounds of donkey and sheep dung, respectively. In multiple choice oviposition bioassays, S. calcitrans laid more eggs in wet sand containing β-citronellene and carvone than in other treatments. The attractiveness of these compounds was confirmed in a field trial, with traps baited with β-citronellene and carvone catching more S. calcitrans. We conclude that gravid female S. calcitrans use semiochemical cues to choose oviposition substrates that maximise offspring fitness.