The bidirectional relationship between homelessness and poor health and the barriers that individuals who experience homelessness face when trying to access healthcare are well documented. There is, however, little Australian research exploring the situation of individuals who experience homelessness in regional contexts and, moreover, from the perspective of service providers. A qualitative descriptive methodology underpinned this study, with in-depth semi-structured interviews being conducted with 11 service providers to identify barriers to care faced by people who experience homelessness and barriers that service providers themselves experience in supporting this population. The key barriers identified were client-level barriers: living day-by-day, financial, health literacy, mental health conditions, behaviour, safety and stigma; provider-level barriers: few bulk-billing doctors, fragmented services, limited resources, negative past experiences with healthcare; and system level barriers: transportation, over-stretched healthcare services. The combined impact of these barriers has significantly contributed to the desperate situation of people experiencing homelessness in Launceston. This situation is likely replicated in other regional populations in Australia. Given that individuals experiencing homelessness have higher rates of every measure in health inequality, steps need to be taken to reduce barriers, and a standardised approach to health care urgently needs to be implemented by governments at the state and national level to improve the health of regionally based individuals experiencing homelessness.