By entering outcome-based service (OBS) relationships, industrial service providers and their customers realign their business interests to achieve mutually beneficial outcomes. The move towards OBS represents a shift from transactional to relational interaction between the providers and their customers. Thus, the changed relationship is bound to envelop paradoxes – circumstances that involve competing demands where making tradeoffs can often be impossible. The purpose of this study is to explore such relational paradoxes in OBS relationships and how providers cope with them. An explorative case study approach reveals that the relational paradoxes are related to control, knowledge, dependency, and complexity. Subsequently, we developed a COPE framework consisting of four provider coping strategies: commitment, openness, partnerships, and extrication. Building on the logic of knotted paradoxes, we introduce a quatrefoil knot in which the found relational paradoxes are enmeshed. Finally, we show how different paradoxical tensions become salient at different phases of the OBS relationship while being reinforced by the latent paradoxes at the time. For managers, we disclose relational tensions and their temporal interplay and suggest strategies to cope with them.