The sustainability problems with regard to the production, distribution, and consumption of goods and services increasingly challenge the legitimacy of corporations. The literature distinguishes three strategies that corporations commonly employ to respond to legitimacy problems: adapt to external expectations, manipulate the perception of their stakeholders, or engage in a discourse with those who question their legitimacy. We discuss three approaches to determine the appropriate response strategy: one-best-way approach, contingency approach, and paradox approach. We argue that in the face of heterogeneous environments with conflicting demands, corporations that follow a paradox approach are likely to be more successful in preserving their legitimacy than those that adopt one of the other two approaches. We develop a theoretical framework for the application of different response strategies and explore the management of paradoxes by way of structural, contextual, or reflective means.