Outcome business models (OBMs) guarantee and deliver economic and operational results for customers. The risk transfer from customer to provider enables the emergence of new value drivers, such as mutual learning. However, if the outcome-based service (OBS) customer learns the operational capabilities, based on which they are willing to rely on the OBS provider to achieve outcomes, how then does an OBS provider justify its role as a legitimate partner in the future? To answer this question, we conducted an in-depth single-case study and performed a critical discourse analysis with an OBS provider delivering outcomes. We identify causes for legitimacy struggles (lack of intentional and competence trust) in an OBM and subsequent discursive legitimation strategies used to defend legitimacy: 1) trustification, 2) rationalization, 3) authorization, and 4) normalization. For managers, we elaborate certain OBM problematics causing legitimacy struggles and offer discursive resources that can be mobilized to recreate legitimacy.