The literature suggests that collaborative governance efforts typically face three types of challenges: substantive problem-solving challenges, collaborative process challenges and multi-relational accountability challenges. In this article, we investigate how these challenges manifest themselves in practice and explore potential ways in which collaborators can deal with them. To do so, we studied eight multi-agency crime-fighting collaborations in the Netherlands using a quasi-experimental action-research approach. We found that the challenges present collaborations with a set of paradoxical demands. Collaborations that were able to make progress transcended the paradoxes by adopting a ‘both/and’ rather than an ‘either/or’ mindset. Our findings contribute to knowledge about designing effective multi-agency collaborations.