The choice of the partner an individual will mate with is expected to strongly impact its fitness. Hence, natural selection has favoured the evolution of cues to distinguish among mates that will provide different fitness benefits to the individual that is choosing. In species with first-male sperm precedence, this is particularly important for males, as mating with mated females will result in no offspring. In the spider mite Tetranychus urticae only the first mating is effective, except if the interval between first and second copulations is shorter than 24 h. In line with this, males prefer to mate with virgin over mated females. They do not, however, choose between females that have mated at different time intervals. Here, we tested which type of cues males use to distinguish between females with different mating status (virgin versus mated). To do so, we firstly confirmed that males prefer virgins over mated females and that they do not select females on the basis of their age or mating interval. Next, we tested whether contact and volatile compounds or chemical trails affected male discrimination between mated and virgin females, by systematically varying the exposure of males to these cues. We found that volatile compounds and chemical trails were sufficient to induce discrimination between virgin and mated females in males. Direct contact with females, however, does not seem to play a role in this discrimination. The composition of such chemical cues (trails and volatiles) remains to be identified.