Gender is increasingly recognized as fundamental to understanding migration processes, causes and consequences. In South Africa, it is intrinsic to the social transformations fueling high levels of internal migration and complex forms of mobility. While female migration in Africa has often been characterized as less prevalent than male migration, and primarily related to marriage, in South Africa a feminization of internal migration is underway, fueled by women's increasing labor market participation. In this paper, we report sex differences in patterns, trends and determinants of internal migration based on data collected in a demographic surveillance system between 2001 and 2006 in rural KwaZulu-Natal. We show that women were somewhat more likely than men to undertake any migration, but sex differences in migration trends differed by migration flow, with women more likely to migrate into the area than men, and men more likely to out-migrate. Out-migration was suppressed by marriage particularly for women, but most women were not married; both men's and women's out-migrations were undertaken mainly for purposes of employment. Over half of female out-migrations (versus 35% of male out-migrations) were to nearby rural areas. The findings highlight the high mobility of this population and the extent to which gender is intimately related to the processes determining migration. We consider the implications of these findings for the measurement of migration and mobility, in particular for health and social policy and research among highly mobile populations in southern Africa.