Nests play a critical role for offspring development across the animal kingdom. Nest quality may contribute to the builder’s extended phenotype and serve as an ornament during mate choice. We examined male and female nest choice in the common goby (Pomatoschistus microps), a benthic fish with male-only parental care where females deposit eggs in male-built nests. Using pre-built nest models, we independently manipulated two candidate nest quality traits, (i) nest entrance width with a role in oxygen ventilation and (ii) extent of sand cover with a role in camouflage. In simultaneous choice trials, male gobies exhibited no preference for any nest model type. This suggests that initial characteristics of a nesting substrate have minor importance for males, which usually remodel the nest. Females were given a choice between two males occupying either entrance- or cover-manipulated nests. The same pair of males was then exposed to a second female but now with alternated nest types assigned. Most females were consistent in choosing the same, typically the heavier male of the two regardless of nest properties. However, the females that chose the same nest regardless of the male preferred low over high sand coverage and narrow over wide nest entrance. Our results indicate that females base their mating decision on a combination of male phenotype and nest traits. While we found no indication that females are attracted to highly decorated nests, our study is the first in fishes to disentangle a preference for narrow (and thus more protective) nest entrances independent of nest coverage.