Most plant-feeding insects are ecological specialists restricted to one or a few closely related host-plant species (Forister et al. 2015). A long-standing hypothesis asserts that natural selection favors host specialization because trade-offs between performance on alternative host species limit the fitness of generalists, yet empirical evidence for such trade-offs is scarce (Futuyma and Moreno 1988; Forister et al. 2012). Here we show that trade-offs between adaptations to alternative hosts occur over both long- and short-term macroevolutionary timescales, but positive associations between host-use traits are also abundant. Host-use records of 1604 caterpillar (Lepidoptera) species revealed negative associations between adaptations to two diverse groups of host-plant taxa over 150 million years (Misof et al. 2014) of caterpillar evolutionary history, but a different division between use of angiosperm and pine hosts among closely related caterpillars. In contrast, host-use records of 955 true bug (Hemiptera) species suggested uniformly positive associations between adaptations to the same host taxa both over the 300-million-year (Misof et al. 2014) evolutionary history of true bugs and among closely related species. The lack of consistent patterns across insect orders and timescales suggests that host-use trade-offs are historically contingent rather than universal constraints, reflecting the diversity of mechanisms driving host-specialization in plant-feeding insects.