A preference to mate with novel partners has been shown for both males and females in a range of taxa. Preferences for novel mates may result from direct recognition of previous sexual partners, or from other cues that predict this, such as familiarity. Costs and benefits of mating with multiple mates differ for males and females. Despite this, few studies have tested whether the sexes differ in their preferences for novel mates. Here, we investigated whether males and/or females showed preferences for novel mates and whether this differed depending on the type of experience with a familiar mate (i.e., previously allowed to mate or allowed visual and olfactory exposure only) in the eastern mosquitofish (Gambusia holbrooki). We show that mosquitofish prefer to associate with novel fish and that there was no significant difference between the sexes in the strength of this preference if the choosing fish had previously had an opportunity to mate. In contrast, males and females that had not recently mated and were familiar due solely to visual and olfactory contact did not have a preference for novel mates. Our results suggest that there are likely to be benefits of mating with multiple partners for both males and females.