In sexually reproducing animals, mating is essential for transmitting genetic information to the next generation and therefore animals have evolved mechanisms for optimizing the chance of successful mate location. In the soil nematode C. elegans, males approach hermaphrodites via the ascaroside pheromones, recognize hermaphrodites when their tails contact the hermaphrodites' body, and eventually mate with them. These processes are mediated by sensory signals specialized for sexual communication, but other mechanisms may also be used to optimize mate location. Here we describe associative learning whereby males use sodium chloride as a cue for hermaphrodite location. Both males and hermaphrodites normally avoid sodium chloride after associative conditioning with salt and starvation. However, we found that males become attracted to sodium chloride after conditioning with salt and starvation if hermaphrodites are present during conditioning. For this conditioning, which we call sexual conditioning, hermaphrodites are detected by males through pheromonal signaling and additional cue(s). Sex transformation experiments suggest that neuronal sex of males is essential for sexual conditioning. Altogether, these results suggest that C. elegans males integrate environmental, internal and social signals to determine the optimal strategy for mate location.