In phytophagous insects such as butterflies, there is an evolutionary trend towards specialization in host plant use. One contributing mechanism for this pattern may be found in female host search behavior. Since search attention is limited, generalist females searching for hosts for oviposition may potentially increase their search efficacy by aiming their attention on a single host species at a time, a behavior consistent with search image formation. Using laboratory reared and mated females of two species of generalist butterflies, the comma, Polygonia c-album, and the painted lady, Vanessa cardui (Lepidoptera: Nymphalidae), we investigated the probability of finding a specific target host (among non-host distractors) immediately after being primed with an oviposition experience of the same host as compared to different host in indoor cages. We used species-specific host plants that varied with respect to growth form, historical age of the butterfly-host association, and relative preference ranking. We found improved search efficacy after previous encounters of the same host for some but not all host species. Positive priming effects were found only in hosts with which the butterfly has a historically old relationship and these hosts are sometimes also highly preferred. Our findings provides additional support for the importance of behavioral factors in shaping the host range of phytophagous insects, and show that butterflies can attune their search behavior to compensate for negative effects of divided attention between multiple hosts.