A major fraction of the diversity of insects is parasitic, as herbivores, parasitoids or vertebrate ectopara sites. Understanding this diversity requires information on the origin of parasitism in various insect groups. Parasitic lice (Phthiraptera) are the only major group of insects in which all members are permanent parasites of birds or mammals. Lice are classified into a single order but are thought to be closely related to, or derived from, book lice and bark lice (Psocoptera). Here, we use sequences of the nuclear 18S rDNA gene to investigate the relationships among Phthiraptera and Psocoptera and to identify the origins of parasitism in this group (termed Psocodea). Maximum-likelihood (ML), Bayesian ML and parsimony analyses of these data indicate that lice are embedded within the psocopteran infraorder Nanopsocetae, making the order Psocoptera paraphyletic (i.e. does not contain all descendants of a single common ancestor). Furthermore, one family of Psocoptera, Liposcelididae, is identified as the sister taxon to the louse suborder Amblycera, making parasitic lice (Phthiraptera) a polyphyletic order (i.e. descended from two separate ancestors). We infer from these results that parasitism of vertebrates arose twice independently within Psocodea, once in the common ancestor of Amblycera and once in the common ancestor of all other parasitic lice.