Moderate heat stress negatively impacts fertility in sexually reproducing organisms at sublethal temperatures. These moderate heat stress effects are typically more pronounced in males. In some species, sperm production, quality and motility are the primary cause of male infertility during moderate heat stress. However, this is not the case in the model nematode Caenorhabditis elegans, where changes in mating behavior are the primary cause of fertility loss. We report that heat-stressed C. elegans males are more motivated to locate and remain on food and less motivated to leave food to find and mate with hermaphrodites than their unstressed counterparts. Heat-stressed males also demonstrate a reduction in motility that likely limits their ability to mate. Collectively these changes result in a dramatic reduction in reproductive success. The reduction in mate-searching behavior may be partially due to increased expression of the chemoreceptor odr-10 in the AWA sensory neurons, which is a marker for starvation in males. These results demonstrate that moderate heat stress may have profound and previously underappreciated effects on reproductive behaviors. As climate change continues to raise global temperatures, it will be imperative to understand how moderate heat stress affects behavioral and motility elements critical to reproduction.