This paper explores the relationship between business experience in cross-sector partnerships (CSPs) and the co-creation of what we refer to as ‘dynamic capabilities for stakeholder orientation,’ consisting of the four dimensions of (1) sensing, (2) interacting with, (3) learning from and (4) changing based on stakeholders. We argue that the co-creation of dynamic capabilities for stakeholder orientation is crucial for CSPs to create societal impact, as stakeholder-oriented organizations are more suited to deal with “wicked problems,” i.e., problems that are large, messy, and complex (Rittel and Webber, Policy Sciences 4:155–169, 1973; Waddock, Paper presented at the 3rd international symposium on cross sector social interactions, 2012). By means of a grounded theory approach of inductive research, we collected and interpreted data on four global agri-food companies which have heterogeneous experience in participating in CSPs. The results of this paper highlight that only companies’ capability of interacting with stakeholders continually increases, while their capabilities of sensing, learning from, and changing based on stakeholders first increase and then decrease as companies gain more experience in CSP participation. To a large extent, this can be attributed to the development of corporate strategies on sustainability after a few years of CSP participation, which entails a shift from a reactive to a proactive attitude towards sustainability issues and which may decrease the need or motivation for stakeholder orientation. These findings open up important issues for discussion and for future research on the impact of CSPs in a context of wicked problems.