Mexicana rubra sp. nov. and Encotyllabe cf. spari are described from the gills of the marine fi sh Orthopristis ruber (Haemulidae) caught off Rio de Janeiro, Brazil. Morphological, ultrastructural and genetic data are provided. The main diagnostic features of this new species of ectoparasite are a posteriorly bipartite testis, a ventral bar with three deep bowed projections and a dorsal bar with two deep, conspicuous, antero-lateral indentations. Genetic data on Mexicana rubra sp. nov. are based on the ITS1, 5.8S and partial 18S and 28S rDNA. This is the sixth known species of Mexicana Caballero & Bravo-Hollis, 1959, a key to which is also presented. Encotyllabe cf. spari Yamaguti, 1934 is described from the same host, with new ultrastructural data and new partial 18S and 28S rDNA sequences. A phylogenetic analysis based on partial 18S and 28S sequences is undertaken for both species.