Nepal is a key supplier of labour for countries in the Middle East, India and Malaysia. As many more men than women leave Nepal to work abroad, female migrant workers are a minority and very much under-researched. The aim of the study was to explore the health problems of female Nepalese migrants working in the Middle-East and Malaysia. The study was conducted among 1010 women who were registered as migrant returnees at an organisation called Pourakhi Nepal. Secondary data were extracted from the records of the organisation covering the five-year period of July 2009 to July 2014. The 1010 participants were aged 14 to 51 with a median age of 31 (IQR: 38-25) years. A quarter of respondents (24%) reported having experienced health problems while in the country of employment. Fever, severe illness and accidents were the most common health problems reported. Working for unlimited periods of time and not being able to change one’s place of work were independently associated with a greater likelihood of health problems. Logistic regression shows that migrant women who are illiterate [OR = 1.56, 95% CI: 1.02 to 2.38, p = 0.042], who had changed their workplace [OR = 1.63, 95% CI: 1.14 to 2.32, p = 0.007], who worked unlimited periods of time [OR = 1.64, 95% CI: 1.44 to 1.93, p = 0.020], had been severely maltreated or tortured in the workplace [OR = 1.84, 95% CI: 1.15 to 2.92, p = 0.010], were not being paid on time [OR = 2.38, 95% CI: 1.60 to 3.55, p = 0.038] and migrant women who had family problems at home [OR = 3.48, CI 95%: 1.22 to 9.98, p = 0.020] were significantly associated with health problems in their host country in the Middle East. Female migrant workers face various work-related health risks, which are often related to exploitation. The Government of Nepal should initiate awareness campaigns about health risks and rights in relation to health care services in the host countries. Recruiting agencies/employers should provide information on health risks and training for preventive measures. Raising awareness among female migrant workers can make a change in their working lives.