Phylograms based on mitochondrial cytochrome oxidase I gene sequences show that the Anoplocephaloides variabilis (Douthitt, 1915)-like cestodes (Cestoda: Anoplocephalidae) from voles (Microtus spp.) and Paranoplocephala krebsi Haukisalmi, Wickström, Hantula & Henttonen, 2001 from collared lemmings (Dicrostonyx spp.) comprise a monophyletic group within the anoplocephaline cestodes. The patterns of phylogenetic, biological and/or biogeographical distinction suggest six or seven species of A. variabilis-like cestodes, including P. krebsi. However, at this time we decline to describe them as a series of new species as no straightforward morphological differences were found between the A. variabilis-like cestodes. A new genus, Microcephaloides n. g., is proposed for the cestodes earlier assigned to A. variabilis, A. cf. variabilis, A. tenoramuraiae Genov & Georgiev, 1988 and P. krebsi. A redescription is provided for the type-species, M. variabilis n. comb., from pocket gophers (Geomys spp. and Thomomys spp.). In addition to Anoplocephaloides Baer, 1927 (sensu stricto) and Microcephaloides, Paranoplocephaloides Gulyaev, 1996, Flabelloskrjabinia Spasskii, 1951 and Leporidotaenia Genov, Murai, Georgiev & Harris, 1990 are considered valid genera among cestodes previously assigned to Anoplocephaloides (sensu Rausch, 1976). The host spectrum and present phylogenetic data suggest that Microcephaloides has been primarily associated with voles (Microtus spp.) and its basal lineage now occurs in M. guentheri (Danford & Alston) in Turkey. Although the distribution and current host of the basal lineage suggest a western Palaearctic origin, subsequent diversification has probably occurred in eastern Beringia, because most of the more derived lineages occur partly or exclusively in Alaska.