Parasites and symbionts of freshwater mussels are poorly understood, although a diverse assemblage of mussel-associated leeches (Glossiphoniidae) was recently described. Here, we report on the discovery of a fish leech (Piscicolidae) in the mantle cavity of the freshwater mussel Cristaria plicata (Unionidae) in the Russian Far East. It is the first member of this leech family being associated with freshwater molluscs. This leech does not match any known genus and species both morphologically and genetically, and is described here as Alexandrobdella makhrovi gen. & sp. nov. It uses mussels as shelter (and probably as a secondary host), while the Amur catfish Silurus asotus (Siluridae) seems to be the primary host. These novel findings indicate that mussel-associated leech assemblage contains at least one piscicolid species. Our fossil-calibrated phylogeny suggests that the crown group of Piscicolidae was originated in the Early Cretaceous. This primarily marine family shares at least five independent colonization events into freshwater environments.