Abstract Background Aboriginal Australians experience poorer outcomes from cancer compared to the non-Aboriginal population. Some progress has been made in understanding Aboriginal Australians’ perspectives about cancer and their experiences with cancer services. However, little is known of cancer service providers’ (CSPs) thoughts and perceptions regarding Aboriginal patients and their experiences providing optimal cancer care to Aboriginal people. Communication between Aboriginal patients and non-Aboriginal health service providers has been identified as an impediment to good Aboriginal health outcomes. This paper reports on CSPs’ views about the factors impairing communication and offers practical strategies for promoting effective communication with Aboriginal patients in Western Australia (WA). Methods A qualitative study involving in-depth interviews with 62 Aboriginal and non-Aboriginal CSPs from across WA was conducted between March 2006 - September 2007 and April-October 2011. CSPs were asked to share their experiences with Aboriginal patients and families experiencing cancer. Thematic analysis was carried out. Our analysis was primarily underpinned by the socio-ecological model, but concepts of Whiteness and privilege, and cultural security also guided our analysis. Results CSPs’ lack of knowledge about the needs of Aboriginal people with cancer and Aboriginal patients’ limited understanding of the Western medical system were identified as the two major impediments to communication. For effective patient–provider communication, attention is needed to language, communication style, knowledge and use of medical terminology and cross-cultural differences in the concept of time. Aboriginal marginalization within mainstream society and Aboriginal people’s distrust of the health system were also key issues impacting on communication. Potential solutions to effective Aboriginal patient-provider communication included recruiting more Aboriginal staff, providing appropriate cultural training for CSPs, cancer education for Aboriginal stakeholders, continuity of care, avoiding use of medical jargon, accommodating patients’ psychosocial and logistical needs, and in-service coordination. Conclusion Individual CSPs identified challenges in cross-cultural communication and their willingness to accommodate culture-specific needs within the wider health care system including better communication with Aboriginal patients. However, participants’ comments indicated a lack of concerted effort at the system level to address Aboriginal disadvantage in cancer outcomes.