Visual cues are important for insects to find flowers and host plants. It has been proposed that the diversity of leaf shape in Passiflora vines could be a result of negative frequency dependent selection driven by visual searching behavior among their butterfly herbivores. Here we tested the hypothesis that Heliconius butterflies use leaf shape as a cue to initiate approach toward a host plant. We first tested for the ability to recognize shapes using a food reward conditioning experiment. Butterflies showed an innate preference for flowers with three and five petals. However, they could be trained to increase the frequency of visits to a non-preferred flower with two petals, indicating an ability to learn to associate shape with a reward. Next we investigated shape learning specifically in the context of oviposition by conditioning females to lay eggs on two shoots associated with different artificial leaf shapes: their own host plant, Passiflora biflora, and a lanceolate non-biflora leaf shape. The conditioning treatment had a significant effect on the approach of butterflies to the two leaf shapes, consistent with a role for shape learning in oviposition behavior. This study is the first to show that Heliconius butterflies use shape as a cue for feeding and oviposition, and can learn shape preference for both flowers and leaves. This demonstrates the potential for Heliconius to drive negative frequency dependent selection on the leaf shape of their Passiflora host plants.