Early colonization by Zyginidia scutellaris leafhoppers might be a key factor in the attraction and settling of generalist predators, such as Orius spp., in maize fields. In this paper, we aimed to determine whether our observations of early season increases in field populations of Orius spp. reflect a specific attraction to Z. scutellaris-induced maize volatiles, and how the responses of Orius predators to herbivore-induced volatiles (HIPVs) might be affected by previous experiences on plants infested by herbivorous prey. Therefore, we examined the innate and learned preferences of Orius majusculus toward volatiles from maize plants attacked by three potential herbivores with different feeding strategies: the leafhopper Z. scutellaris (mesophyll feeder), the lepidopteran Spodoptera littoralis (chewer), and another leafhopper Dalbulus maidis (phloem feeder). In addition, we examined the volatile profiles emitted by maize plants infested by the three herbivores. Our results show that predators exhibit a strong innate attraction to volatiles from maize plants infested with Z. scutellaris or S. littoralis. Previous predation experience in the presence of HIPVs influences the predator’s odor preferences. The innate preference for plants with cell or tissue damage may be explained by these plants releasing far more volatiles than plants infested by the phloem-sucking D. maidis. However, a predation experience on D. maidis-infested plants increased the preference for D. maidis-induced maize volatiles. After O. majusculus experienced L3-L4 larvae (too large to serve as prey) on S. littoralis-infested plants, they showed reduced attraction toward these plants and an increased attraction toward D. maidis-infested plants. When offered young larvae of S. littoralis, which are more suitable prey, preference toward HIPVs was similar to that of naive individuals. The HIPVs from plants infested by herbivores with distinctly different feeding strategies showed distinguishable quantitative differences in (Z)-3-hexenal, (E)-2-hexenal, and methyl salicylate. These compounds might serve as reliable indicators of prey presence and identity for the predator. Our results support the idea that feeding by Z. scutellaris results in the emission of maize’s HIPVs that initially recruit Orius spp. into maize fields.