Sexual cues, including extended phenotypes, are expected to be reliable indicators of male genetic quality and/or provide information on parental quality. However, the reliability of these cues may be dependent on stability of the environment, with heterogeneity affecting how selection acts on such traits. Here we test how environmental change mediates mate choice for multiple sexual traits, including an extended phenotype – the structure of male-built nests – in stickleback fish. First, we manipulated the dissolved oxygen (DO) content of water to create high or low DO environments in which male fish built nests. Then we recorded the mate choice of females encountering these males (and their nests), under either the same or reversed DO conditions. Males in high DO environments built more compact nests than those in low DO conditions and males adjusted their nest structure in response to changing conditions. Female mate choice for extended phenotype (male nests) was environmentally-dependent (females chose more compact nests in high DO conditions), while female choice for male phenotype was not (females chose large, vigorous males regardless of DO level). Examining mate choice in this dynamic context suggests that females evaluate the reliability of multiple sexual cues, taking into account environmental heterogeneity.