The colonization of exotic plants by herbivorous insects has provided opportunities for investigating causes and consequences associated with the evolution of niche breadth. The butterfly Lycaeides melissa utilizes exotic alfalfa, Medicago sativa, which is a relatively poor larval resource, and previous studies have found that caterpillars that consume M. sativa develop into smaller and less fecund adults. Here we investigate the effect of smaller female body size on male mate preference, a previously unexplored consequence of novel host use. Smaller females, which developed on the exotic host, were less likely to be visited by males. This result was confirmed with a second set of choice tests involving females reared on a single plant species, thus ruling out host-specific confounding factors. We suggest that an effect on mate choice be considered as part of the complex suite of factors determining persistence of herbivorous insects following colonization of new habitats or resources.