In contrast to what is known about adaptive mate choice in females, we know far less about how fluctuating reproductive costs might affect male mate choice. In many species, sperm competition can have a direct bearing on male fertilization success, and choosy males should be expected to respond adaptively to the perceived cost of sperm competition and to adjust their mate preferences accordingly. Here, we conducted a series of experiments investigating male mate choice under sperm competition risk in the eastern mosquito fish, Gambusia holbrooki. We tested male association preferences before and after manipulating their perceptions of sperm competition risk associated with initially preferred and nonpreferred females. We found that individuals were consistent in their preferences if they did not have the opportunity to witness other males associating with the initially preferred female. By contrast, males spent significantly less time with initially preferred females if, in the interim, she had been seen in the vicinity of another male. A similar opportunity to observe the initially nonpreferred female with another male had no effect on subsequent male mate choice. Our results suggest that choosy males may be capable of adjusting their preferences in response to shifts in their perception of sperm competition risk.