The type species of the cestode genus Arostrilepis Mas-Coma et Tenora, 1997, Arostrilepis horrida (Linstow, 1901), is redescribed on the basis of the syntype material from the brown rat (Rattus norvegicus) deposited in the collection of the Museum für Naturkunde, Berlin. Arostrilepis horrida (sensu lato), reported from a wide range of rodents throughout the Holarctic Region, is shown to be a species complex. The proposed host range and geographical distribution of A. horrida (sensu stricto) are limited to the data reported in the original description. The previously proposed synonymy of A. horrida is examined and the following species are excluded from the list of its synonyms: Hymenolepis procera Janicki, 1904, H. arvicolina Cholodkowsky, 1913, H. sciurina Cholodkowsky, 1913 and H. mathevossianae Akhumyan, 1946; these are considered species inquirendae. Specimens previously identified as A. horrida from voles from the Asian part of Russia are revised and newly collected materials are worked out. Two new species, A. macrocirrosa sp. n. and A. tenuicirrosa sp. n., are described. The main differentiating characters used to distinguish Arostrilepis spp. are the form and size of cirrus and its armature as well as the type of arrangement for the testes. The new species can also be distinguished from one another on the basis of sequences of the ITS2 rRNA gene. The generic diagnosis of Arostrilepis is emended. Hymenolepis neurotrichi Rausch, 1962, which had been placed in Arostrilepis by Mas-Coma and Tenora (1997), does not correspond to the generic diagnosis and is considered a species incertae sedis.