Focusing on migrants from Uzbekistan and Tajikistan in Russia, where there are high levels of both immigration and gender inequality, this paper exploits unique data collected by the authors recording detailed information on health and migration trajectories. We find that migrant women are on average in poorer health than migrant men. This gender gap is only partly explained by gender differences in observed socioeconomic, demographic, living and working characteristics and differences in pre-migration health. We show that migrant women’s health is more likely than men’s to deteriorate during migration. This women’s health disadvantage is sensitive to the migration profile, as it only appears after a certain time spent migrating and for migrants with a vulnerable legal status.