A fundamental prediction of reproductive signal evolution is that selection should favor male courtship signals that are conspicuous with respect to the surrounding media. However, many species live in heterogeneous environments where spatiotemporal variability can degrade the efficacy of signals tuned to specific conditions. One rarely considered solution to this problem is to evolve generalized signals that can effectively transmit information under most of the conditions that are likely to be encountered. Here, I present results from a study of a freshwater fish, the brook stickleback (Culaea inconstans) that are consistent with the hypothesis that sexually dimorphic body coloration has been driven by selection for conspicuousness under multiple environmental conditions. In choice tests, females showed no bias favoring a conspicuous black stimulus in simulated oligotrophic stream conditions, but showed a strong and equal bias for the black phenotype in simulated dystrophic and eutrophic streams. These data indicate that the evolution of signals that maximize achromatic contrast with the surrounding environment may be an effective mechanism for maintaining conspicuousness in heterogeneous visual environments. The repeated evolution of black color signals by stream fishes may therefore represent a specific example of this general evolutionary mechanism.