Entomoparasitic nematodes are natural control agents for many insect pests, including fleas that transmit Yersinia pestis, a causative agent of plague, in the natural foci of this extremely dangerous zoonosis. We examined the flea samples from the Volga-Ural natural focus of plague for their infestation with nematodes. Among the six flea species feeding on different rodent hosts (Citellus pygmaeus, Microtus socialis, and Allactaga major), the rate of infestation varied from 0 to 21%. The propagation rate of parasitic nematodes in the haemocoel of infected fleas was very high; in some cases, we observed up to 1,000 juveniles per flea specimen. Our study of morphology, life cycle, and rDNA sequences of these parasites revealed that they belong to three distinct species differing in the host specificity. On SSU and LSU rRNA phylogenies, these species representing three genera (Rubzovinema, Psyllotylenchus, and Spilotylenchus), constitute a monophyletic group close to Allantonema and Parasitylenchus, the type genera of the families Allantonematidae and Parasitylenchidae (Nematoda: Tylenchida). We discuss the SSU-ITS1-5.8S-LSU rDNA phylogeny of the Tylenchida with a special emphasis on the suborder Hexatylina.