The high rates of youth migration to urban and economic centers, in the context of persistent poverty and devastating HIV/AIDS burden, have raised intricate social policy challenges in developing countries. Using the 2008 Nigeria Demographic and Health Survey data, descriptive statistics, Kaplan–Meier survival curves and discrete-time hazard regression models, this study examines the patterns of internal migration and sexual initiation among never-married Nigerian youth aged 15–24. We find that migrants generally show stronger association than non-migrants, and urban–rural and rural–rural migrants particularly show the strongest independent association with premarital sexual initiation. Other significant covariates are age, religion, ethnic origin, educational attainment, independent living arrangement, formal employment and exposure to the mass media. The findings highlight the direct importance of youth migration in understanding and addressing the challenges of premarital sexual behavior and the need for behavior change policies and programs to be sensitive to the complex contextual nuances across youth groups in one country.