Prison leavers encounter significant barriers to successfully re-integrating into the community, which can lead to re-offending. Complex interventions which are multi-faceted and involve successful partnerships are needed to meet the distinct health and social needs of this population group. For this study, we conducted a process evaluation of a pilot project, which aimed to offer holistic support to prison leavers through a combination of peer mentoring, sport and physical activity, and signposting, delivered in a community setting. Semi-structured interviews and focus groups were conducted with individuals (n = 14) involved in the delivery and the management of the project to understand how it had been implemented and what factors had influenced the delivery and partnerships involved. Factors that influenced project delivery included safeguarding and risk assessment concerns, lived experience of peer mentors, accessibility of the intervention, and the role of sport and physical activity as a vehicle for community re-integration. Partnership working was influenced by effective information sharing, organizational commitment, building relationships and professional networks, and regular communication between organizations. An intervention involving peer mentoring, sport and physical activity, and signposting, supported by close partnership working, was viewed as a promising approach to support the community re-integration of prison leavers.