We test the idea that male colour polymorphism in a lizard (red vs. yellow headed) may be maintained by a female preference for associating (and presumably mating) with both male morphs rather than only one. In female choice experiments on single males of different colours, females did not preferentially associate with either morph. However, when females were allowed to choose between pairs of males of the same vs. different colours, they preferred to associate with male pairs that were polymorphic. We suggest that this may be the result of selection arising from polyandrous mating benefits and show experimentally that polyandry results in increased hatching success. Most theoretical models of the evolution of mate choice assume that mate choice is costly. We test this assumption by releasing females into polymorphic vs. monomorphic groups in the wild, under the hypothesis that females move more between males in polymorphic groups and therefore suffer higher risks of mortality from predation. In accordance with this prediction, females released into polymorphic male groups were less likely to be recaptured than females released into monomorphic groups, with evidence to suggest that this is because of increased mortality and not increased dispersal. We propose that this cost could be (partly) balanced by polyandrous fitness benefits.