The aim of this study was to explore how people’s sexual history affects their attractiveness. Using an Internet survey, 188 participants rated their willingness to engage in a relationship with a hypothetical individual with a specified number of past sexual partners, ranging from 0 to 60+. The effect of past partner number was very large. Average willingness ratings initially rose as past partner number rose, but then fell dramatically. For short-term relationships, men were more willing than women to get involved (although the difference was not large). For long-term relationships, in contrast, there was virtually no sex difference. Thus, contrary to the idea that male promiscuity is tolerated but female promiscuity is not, both sexes expressed equal reluctance to get involved with someone with an overly extensive sexual history. Finally, participants with an unrestricted sociosexual orientation (high SO participants) were more tolerant than low SO participants of prospective mates with higher numbers of past sexual partners but were also less tolerant of prospective mates with low numbers of past sexual partners.