Male choice is expected to evolve when females differ in quality, even if male investment in each mating is low. The family Poeciliidae is an example of fishes in which males show little parental investment as they only provide sperm. Up until now, a preference for large females has been found in all species studied. Here we show that unexpectedly, males of the least killifish (Heterandria formosa) prefer to interact with small instead of large females in a dichotomous male choice test, even though large females are more fecund. During a free-swimming choice experiment, males did not discriminate between females based on their size. We suggest that this unique preference for small females, or the lack of preference for large females, results from strong first male sperm precedence in this species. Smaller females are younger and therefore more likely to be virgin, which probably makes them more profitable mates for males. When presented with a virgin and a mated female of similar size, males showed no preference for either type. This suggests that males do not use pheromone cues to assess female mating status but that they are likely to use female size as a proxy for it.