Bitterling fishes deposit their eggs on the gills of living mussels using a long ovipositor. We examined whether ovipositor length and egg shape correlated with differences in host mussel species in the family Unionidae among populations of the tabira bitterling (Acheilognathus tabira) in Japan. Bitterling populations that use mussels in the sub-family Anodontinae possessed longer ovipositors and more elongated eggs than those using mussels of Unioninae, as expected from the difference in host size between the sub-families (anodontine mussels are larger than unionine mussels). Based on a robust phylogeny of A. tabira populations, we demonstrated that the evolution of both ovipositor length and egg shape were correlated with host differences, but not with each other, suggesting that these traits have been selected for independently. Our study demonstrates how adaptive traits for brood parasitism may diverge with host shift due to different host availability and/or interspecific competition for hosts.