Background: In Australia, Aboriginal children experience significantly poorer health outcomes compared with non-Aboriginal children. Health policies aimed at improving Aboriginal health outcomes include interventions in the early childhood period. There is a need for government health services to work in partnership with Aboriginal people and other services to achieve the highest level of health possible for Aboriginal children, who often require a range of services to meet complex needs. Aim: This paper describes the views of service providers on how paediatric outreach services work in partnership with other services, Aboriginal families and the community and how those partnerships could be improved to maximize health outcomes for children. Methods: In-depth, semi-structured interviews and focus groups were conducted with managers and service providers over a 6-week period in 2010. The views and suggestions of participants were documented and a thematic analysis was undertaken. Results and Discussion: Analysis of two focus groups with seven service providers and five individual interviews with service managers resulted in the identification of four themes: (i) using informal and formal ways of working; (ii) cultivating effective relationships; (iii) demonstrating cultural sensitivity; and (iv) forging strong leadership. Use of formal and informal approaches facilitated effective relationships between service providers and Aboriginal families and communities. Partnerships with the community were founded on a culturally appropriate model of care that recognized a holistic approach to health and wellness. Leadership emerged as an essential component of effective partnerships, cultivating the ethos of the workplace and creating an environment where collaboration is supported. Conclusion: Culturally appropriate child health services, which utilize effective relationships and employ a range of informal and formal collaboration with other services and community members, are well positioned to implement health policy and improve access to services for Aboriginal children with better health outcomes as a result.