Sucking lice of the parvorder Anoplura are permanent ectoparasites with specific lifestyle and highly derived features. Currently, genomic data are only available for a single species, the human louse Pediculus humanus. Here, we present genomes of two distinct lineages, with different host spectra, of a rodent louse Polyplax serrata. Genomes of these ecologically different lineages are closely similar in gene content and display a conserved order of genes, with the exception of a single translocation. Compared with P. humanus, the P. serrata genomes are noticeably larger (139 vs. 111 Mbp) and encode a higher number of genes. Similar to P. humanus, they are reduced in sensory-related categories such as vision and olfaction. Utilizing genome-wide data, we perform phylogenetic reconstruction and evolutionary dating of the P. serrata lineages. Obtained estimates reveal their relatively deep divergence (∼6.5 Mya), comparable with the split between the human and chimpanzee lice P. humanus and Pediculus schaeffi. This supports the view that the P. serrata lineages are likely to represent two cryptic species with different host spectra. Historical demographies show glaciation-related population size (Ne) reduction, but recent restoration of Ne was seen only in the less host-specific lineage. Together with the louse genomes, we analyze genomes of their bacterial symbiont Legionella polyplacis and evaluate their potential complementarity in synthesis of amino acids and B vitamins. We show that both systems, Polyplax/Legionella and Pediculus/Riesia, display almost identical patterns, with symbionts involved in synthesis of B vitamins but not amino acids.