Although leaving statutory out-of-home care can be a challenging time for many young people, it is recognised that young people who have multiple or complex needs find this transition particularly difficult. This study aims to gain a deeper understanding of the challenges faced by care leavers who have complex needs, as well as to identify some of the best strategies for assisting this population to engage with services and make the transition successfully. Semi-structured individual interviews and focus groups (n = 29) were conducted with 66 individuals who were working in organisations (both government and non-government) that have knowledge of, or contact with, young people leaving care in South Australia. Responses were analysed thematically in relation to the principal challenges and needs of care leavers and the best strategies for encouraging service engagement. The principal challenges related to difficulties in matching the structure of formal services to a population with highly unstructured living arrangements, a history of problematic engagement with the care system and difficulties in social interactions. A set of suggestions for improving service engagement was developed. This included the need for flexible and persistent services, creative, indirect and person-centred approaches to engagement that emphasised the importance of building peer and adult relationships, and developing adaptive life-skills.