Abstract The success of cross-sector collaborations (CSCs) in cities is mixed, and important questions remain about what distinguishes effective from ineffective collaborations. This comparative case study examined nine CSCs in three US cities, focusing on three public policy areas: education, economic development, and public safety. Nine group interviews, 110 individual interviews, and analysis of archival documents revealed common patterns that allow us to build grounded theory about the roots of CSC success. We propose that how a collaboration responds to setbacks plays a crucial role. Success arises in collaborations that respond to setbacks with a process of mutual learning, in which participants anticipate each other’s actions, devise new ways of apportioning labor, and approach problems collectively. In contrast, failure follows when setbacks lead collaborations into a process of mutual blaming. No single mode of network governance is especially associated with success, but more successful collaborations tend to be characterized by adaptability concerning governance mode. Mutual learning appears to be facilitated by a few key actions: building on prior relationships, relying on trusted key participants, engaging with the community, using data to advantage, and investing in joint problem-solving. Our findings suggest that collaborative leaders in public, private, and nonprofit organizations should emphasize these key actions to enable collaboration and facilitate mutual learning.