Shifts in host-plant use by phytophagous insects have played a central role in their diversification. Evolving host-use strategies will reflect a trade-off between selection pressures. The ecological niche of herbivorous insects is partitioned along several dimensions, and if populations remain in contact, recombination will break down associations between relevant loci. As such, genetic architecture can profoundly affect the coordinated divergence of traits and subsequently the ability to exploit novel habitats. The closely related species Heliconius cydno and H. melpomene differ in mimetic colour pattern, habitat and host-plant use. We investigate the selection pressures and genetic basis underlying host-use differences in these two species. Host-plant surveys reveal that H. melpomene specializes on a single species of Passiflora. This is also true for the majority of other Heliconius species in secondary growth forest at our study site, as expected under a model of interspecific competition. In contrast, H. cydno, which uses closed-forest habitats where both Heliconius and Passiflora are less common, appears not to be restricted by competition and uses a broad selection of the available Passiflora. However, other selection pressures are likely involved, and field experiments reveal that early larval survival of both butterfly species is highest on Passiflora menispermifolia, but most markedly so for H. melpomene, the specialist on that host. Finally, we demonstrate an association between host-plant acceptance and colour pattern amongst interspecific hybrids, suggesting that major loci underlying these important ecological traits are physically linked in the genome. Together, our results reveal ecological and genetic associations between shifts in habitat, host use and mimetic colour pattern that have likely facilitated both speciation and coexistence.