A new genus, Mystocestus, is proposed to accommodate a new species, Mystocestus anindoi n. g., n. sp. from Mystus vittatus (Bloch) (type host) in West Bengal and Mystus cavasius (Hamilton) (Siluriformes: Bagridae) in Maharashtra, India. The new genus is most similar to Lucknowia Gupta, 1961 in the shape of the body, which is elongate, slightly tapering towards the anterior end, and scolex, which is digitiform, but differs in the shape of the ovary, which is H-shaped (vs. inverted A-shaped in Lucknowia), the absence of a seminal receptacle (present in Lucknowia) and exclusively cortical vitelline follicles (vs. some follicles in the medulla in the latter genus). Molecular data support the erection of the new genus and place it close to Bovienia Fuhrmann, 1931, species of which can be easily distinguished by exclusively lateral vitelline follicles (lateral and median in the new genus), the presence of a seminal receptacle (absent in Mystocestus) and scolex shape (digitiform, with blunt or slightly concave anterior edge in the new genus vs. small, unspecialized or spatulate in Bovienia). The convoluted taxonomy of tapeworms placed in Mystoides Mathur, 1992 is critically reviewed to clean up taxonomic chaos in Indo-Malayan caryophyllideans. Mystoides was erected in an unpublished PhD thesis and thus its generic name becomes unavailable and also, its type species is conspecific with Lucknowia fossilisi Gupta, 1961 from the stinging catfish, Heteropneustes fossilis (Bloch). Other species of this genus are also conspecific with L. fossilisi. In addition, specific names of most of these taxa are unavailable because they were described in unpublished theses or conference abstracts. Based on recent revisions of Indo-Malayan caryophyllideans, the following nine genera with 15 species are considered valid (numbers of species of individual genera are provided in parentheses): Bovienia (3), Djombangia (1), Lucknowia (2), Lytocestus (2), Mystocestus (1), Pseudocaryophyllaeus (2) (all family Lytocestidae); Adenoscolex (1), Lobulovarium (2), Paracaryophyllaeus (1) (all family Caryophyllaeidae).