The number of migrants has increased globally. This phenomenon has contributed to increasing health problems amongst migrants in high-income countries, including vulnerability for HIV acquisition and other sexual health issues. Adaptation processes in destination countries can present difficulties for migrants to seek help from and gain access to health services. This study examined migrants’ from sub-Saharan Africa (SSA) and South East Asia (SEA) sexual health help-seeking behavior in high-income countries with universal health coverage. The systematic review followed PRISMA guidelines and was registered with PROSPERO. Several databases were searched from 2000 to 2017. Of 2824 studies, 15 met the inclusion criteria. These consisted of 12 qualitative and three quantitative studies conducted in Australia, Spain, the United Kingdom, Belgium, Scotland, Ireland, and Sweden. Migrants experienced a range of difficulties accessing health services, specifically those related to sexual health, in high-income countries. Few studies described sources of sexual health help-seeking or facilitators to help-seeking. Barriers to access were numerous, including: stigma, direct and indirect costs, difficulty navigating health systems in destination countries and lack of cultural competency within health services. More culturally secure health services, increased health service literacy and policy support to mitigate costs, will improve health service access for migrants from SSA and SEA. Addressing the structural drivers for stigma and discrimination remains an ongoing and critical challenge.