Male parental care is typically thought to come at a cost to mate attraction and future mating success. However, it has also been hypothesized that paternal care may be under sexual, as well as natural, selection, such that good fathers actually attract more mates. Here we show experimentally that in the sand goby, Pomatoschistus minutus, females prefer to mate with males that provide higher levels of parental care. We manipulated male behavior using (1) different nest sizes and (2) an application of low-O2 water in the nests, and found that females consistently preferred males with elevated levels of care in dichotomous mate choice tests. This complements our earlier study in which we showed that males increase the amount and quality of care they provide in the presence of females. Our results demonstrate that male care may have evolved as a result of sexual selection rather than natural selection alone, and furthermore, that male care may not necessarily be in conflict with mate attraction.