Animals must find and select mates in environments that naturally vary in both space and time. Of particular importance for many species are the availability and phenology of host plants for feeding and oviposition sites. Here, we used Murgantia histrionica (Hahn) (Hemiptera: Pentatomidae), a herbivorous insect, to determine mating preferences and success using mating assays and preferences based on odor cues. We manipulated the natal and encounter contexts using two different host plants, mustard and broccoli. We found that both the natal host plant and the host plant where insects encountered potential mates significantly affected mating success in this insect. Broccoli-reared individuals were more likely to mate in general; however, all individuals were more likely to mate when placed in an encounter context of mustard. Using a separate assay, we also found that the natal host plant affected female preference based on odor cues; females preferred the odors of males from the same natal environment that the females experienced as nymphs. In addition, we examined color and body size for host plant effects as both size and color are important factors for many species during mate choice. We found that individuals reared on mustard were larger than those reared on broccoli. However, the proportion of orange color on the dorsum of insects was not significantly affected by the natal host plant. In summary, these results suggest that changes in host plants, as commonly occurs seasonally, may have implications for sexual selection via mate choice.