Cochimibdella mexicana n. gen. n. sp. is described based on morphological data and comparative analysis of DNA sequences, including two mitochondrial (cytochrome oxidase subunit I and 12s rRNA) and nuclear (18S rRNA and 28S rRNA) loci. Leech specimens were found in the mantle cavity and external surface of the octopus Octopus bimaculatus from Bahía de los Ángeles, Baja California, México. In vivo observations of recently hatched leeches in the laboratory confirm a broad prey range, including fishes, the most common hosts of the family species. The new taxon differs from species of the family Piscicolidae in possession of weakly developed tubercles in a3 of the urosome. In addition, molecular analysis places Cochimibdella mexicana n. gen. n. sp. sister to Austrobdella californiana and Myzobdella lugubris. This work amends a previous record of the elasmobranch-feeding leech Pontobdella (=Stibarobdella) moorei as a parasite of Octopus bimaculatus from the type locality of the new taxon.