BACKGROUND: Malaysia is widely credited to have achieved universal health coverage for citizens. However, the accessibility of healthcare services to migrant workers is questionable. Recently, medical fees for foreigners at public facilities were substantially increased. Mandatory health insurance only covers public hospital admissions and excludes undocumented migrants. This study explores barriers to healthcare access faced by documented and undocumented migrant workers in Malaysia. METHODS: We use qualitative data from 17 in-depth interviews conducted with key informants from civil society organisations, trade unions, academia, medical professionals, as well as migrant workers and their representatives. We interviewed doctors working in public hospitals and private clinics frequented by migrants. Data were analysed using thematic analysis. RESULTS: We found that healthcare services in Malaysia are often inaccessible to migrant workers. Complex access barriers were identified, many beyond the control of the health sector. Major themes include affordability and financial constraints, the need for legal documents like valid passports and work permits, language barriers, discrimination and xenophobia, physical inaccessibility and employer-related barriers. Our study suggests that government mandated insurance for migrant workers is insufficient in view of the recent increase in medical fees. The perceived close working relationship between the ministries of health and immigration effectively excludes undocumented migrants from access to public healthcare facilities. Language barriers may affect the quality of care received by migrant workers, by inadvertently resulting in medical errors, while preventing them from giving truly informed consent. CONCLUSIONS: We propose instituting migrant-friendly health services at public facilities. We also suggest implementing a comprehensive health insurance to enable healthcare access and financial risk protection for all migrant workers. Non-health sector solutions include the formation of a multi-stakeholder migration management body towards a comprehensive national policy on labour migration which includes health.