Background: While participatory social network analysis can help health service partnerships to solve problems, little is known about its acceptability in cross-cultural settings. We conducted two case studies of chronic illness service partnerships in 2007 and 2008 to determine whether participatory research incorporating social network analysis is acceptable for problem-solving in Australian Aboriginal health service delivery. Methods. Local research groups comprising 13-19 partnership staff, policy officers and community members were established at each of two sites to guide the research and to reflect and act on the findings. Network and work practice surveys were conducted with 42 staff, and the results were fed back to the research groups. At the end of the project, 19 informants at the two sites were interviewed, and the researchers conducted critical reflection. The effectiveness and acceptability of the participatory social network method were determined quantitatively and qualitatively. Results: Participants in both local research groups considered that the network survey had accurately described the links between workers related to the exchange of clinical and cultural information, team care relationships, involvement in service management and planning and involvement in policy development. This revealed the function of the teams and the roles of workers in each partnership. Aboriginal workers had a high number of direct links in the exchange of cultural information, illustrating their role as the cultural resource, whereas they had fewer direct links with other network members on clinical information exchange and team care. The problem of their current and future roles was discussed inside and outside the local research groups. According to the interview informants the participatory network analysis had opened the way for problem-solving by putting issues on the table. While there were confronting and ethically challenging aspects, these informants considered that with flexibility of data collection to account for the preferences of Aboriginal members, then the method was appropriate in cross-cultural contexts for the difficult discussions that are needed to improve partnerships. Conclusion: Critical reflection showed that the preconditions for difficult discussions are, first, that partners have the capacity to engage in such discussions, second, that partners assess whether the effort required for these discussions is balanced by the benefits they gain from the partnership, and, third, that boundary spanning staff can facilitate commitment to partnership goals.