Joint group membership is of major importance for cooperation in humans, and close ties or familiarity with a partner are also thought to promote cooperation in other animals. Here, we present the opposite pattern: female cleaner fish, Labroides dimidiatus, behave more cooperatively (by feeding more against their preference) when paired with an unfamiliar male rather than with their social partner. We propose that cooperation based on asymmetric punishment causes this reversed pattern. Males are larger than and dominant to female partners and are more aggressive to unfamiliar than to familiar female partners. In response, females behave more cooperatively with unfamiliar male partners. Our data suggest that in asymmetric interactions, weaker players might behave more cooperatively with out-group members than with in-group members to avoid harsher punishment.