Aphidinae is the most diverse major lineage of aphids (Aphididae). Aphidinae currently dominate the temperate, northern-hemisphere fauna, but only since the late Tertiary, and few species are native to the southern hemisphere. The success of Aphidinae may be linked to the evolution of an unusual life cycle, host alternation. The classification and phylogeny of Aphidinae have been controversial; schemes based on morphology have been confounded by widespread homoplasy. Here we present the first phylogenetic study of higher-level Aphidinae relationships based on molecular data (elongation factor-1alpha, leucine tRNA, and cytochrome oxidase II sequences). Analyses supported the monophyly of Aphidini and its subtribes, Aphidina and Ropalosiphina, but revealed novel relationships concerning Pterocommatini and Macrosiphini, with the former nested within the latter tribe as the sister to Cavariella. Several relationships within Pterocommatini + Macrosiphini corresponded better with host-plant affiliations than with aphid classification. Overall, relationships found here challenge several traditional views of Aphidinae evolution: they suggest more than one origin of host alternation in the family, and they question the assumption that Aphidinae originated in the northern hemisphere.