Cleaner mutualisms on coral reefs, where specialized fish remove parasites from many species of client fishes, have greatly increased our understanding of mutualism, yet we know little about important interspecific interactions between cleaners. Here, we explore the potential for competition between the cleaners Labroides dimidiatus and Labroides bicolor during two distinct life stages. Previous work has demonstrated that in contrast to L. dimidiatus, which establish cleaning stations, adult L. bicolor rove over large areas, searching for clients. We show that site-attached juvenile L. bicolor associate with different microhabitat than juvenile L. dimidiatus and that L. bicolor specialize on a narrower range of species than L. dimidiatus as both juveniles and adults. Further, we present evidence suggesting that differences in resource use are influenced by competitive interactions between the two species. Finally, we discuss the implications of these results for understanding the ecology and evolution of the mutualism.