Rarely are the evolutionary origins of mate preferences known, but, recently, the preference of female guppies (Poecilia reticulata) for males with carotenoid-based sexual coloration has been linked to a sensory bias that may have originally evolved for detecting carotenoid-rich fruits. If carotenoids enhance the immune systems of these fishes, as has been suggested for other species, this could explain the origin of the attraction to orange fruits as well as the maintenance of the female preference for orange males. We used the classic immunological technique of tissue grafting to assay a component of the immune response of guppies raised on two different dietary levels of carotenoids. Individual scales were transplanted between pairs of unrelated fishes, creating reciprocal allografts. Transplanted scales were scored on a six-point rejection scale every day for 10 days. Five days later, the same pairs of fishes received a second set of allografts and were scored again. Compared with low-carotenoid-diet males, high-carotenoid-diet males mounted a significantly stronger rejection response to the second allograft but not to the first allograft. High-carotenoid-diet females, however, showed no improvement in graft rejection compared with low-carotenoid-diet females. To our knowledge, this is the first experimental evidence for sex-specific effects of carotenoid consumption on the immune system of a species with carotenoid-based sexual coloration. These results are consistent with the hypothesis that the mate preference for carotenoid coloration is maintained by the benefits to females of choosing healthy mates, but they cast doubt on the idea that the benefits of carotenoid consumption, per se, could account for the origin of the preference. The sex-specificity of carotenoid effects on allograft rejection in guppies provides indirect support for the general hypothesis that males pay an immunological cost for sexual ornamentation.