Mate-searching success is a critical precursor to mating, but there is a dearth of research on traits and tactics that confer a competitive advantage in finding potential mates. Theory and available empirical evidence suggest that males locate mates using mate-attraction signals produced by receptive females (personal information) and avoid inadvertently-produced cues from rival males (social information) that indicate a female has likely already mated. Here we show that western black widow males use both kinds of information to find females efficiently, parasitizing the searching effort of rivals in a way that guarantees competition over mating after reaching a female’s web. This tactic may be adaptive because female receptivity is transient, and we show that (a) mate searching is risky (88% mortality) and (b) a strongly male-biased operational sex ratio (from 1.2:1 to >10:1) makes competition inevitable. Males with access to rivals’ silk trails moved at higher speeds than those with only personal information, and located females even when personal information was unreliable or absent. We show that following rivals can increase the potential for sexual selection on females as well as males and argue it may be more widespread in nature than is currently realized.