Animals often express behavioral preferences for different types of food or other resources, and these preferences can evolve or shift following association with novel food types. Shifts in preference can involve at least two phenomena: a change in rank preference or a change in specificity. The former corresponds to a change in the order in which hosts are preferred, while a shift in specificity can be an increase in the tendency to utilize multiple hosts. These possibilities have been examined in relatively few systems that include extensive population-level replication. The Melissa blue butterfly, Lycaeides melissa, has colonized exotic alfalfa, Medicago sativa, throughout western North America. We assayed host preferences of 229 females from 10 populations associated with novel and native hosts. In four out of five native-associated populations, a native host was preferred over the exotic host, while preference for a native host characterized only two out of five of the alfalfa-associated populations. Across all individuals from alfalfa-associated populations, there appears to have been a decrease in specificity: females from these populations lay fewer eggs on the native host and more eggs on the exotic relative to females from native-host populations. However, females from alfalfa-associated populations did not lay more eggs on a third plant species, which suggests that preferences for specific hosts in this system can potentially be gained and lost independently. Geographic variation in oviposition preference in L. melissa highlights the value of surveying a large number of populations when studying the evolution of a complex behavioral trait.