For decades, biologists have debated why many parasites have obligate multi-host life cycles. Here, we use comparative phylogenetic analyses of aphids to evaluate the roles of ecological optimization and historical constraint in the evolution of life cycle complexity. If life cycle complexity is adaptive, it should be evolutionarily labile, i.e., change in response to selection. We provide evidence that this is true in some aphids (aphidines), but not others (non-aphidines) – groups that differ in the intensity of their relationships with primary hosts. Next, we test specific mechanisms by which life cycle complexity could be adaptive or a constraint. We find that among aphidines there is a strong association between complex life cycles and polyphagy but only a weak correlation between life cycle complexity and reproductive mode. In contrast, among non-aphidines the relationship between life cycle complexity and host breadth is weak but the association between complex life cycles and sexual reproduction is strong. Thus, although the adaptiveness of life cycle complexity appears to be lineage specific, across aphids, life cycle evolution appears to be tightly linked with the evolution of other important natural history traits.