BACKGROUND: Tobacco smoking and poor mental health are both prevalent and detrimental health problems in young women. The temporal relationship between the two variables is unclear. We investigated the prospective bi-directional relationship between smoking and mental health over 13 years. METHOD: Participants were a randomly selected community sample of 10 012 young women with no experience of pregnancy, aged 18-23 years at baseline (1996) from the Australian Longitudinal Study on Women's Health. Follow-up surveys over 13 years were completed in 2000, 2003, 2006 and 2009, allowing for five waves of data. Measures included self-reported smoking and mental health measured by the Mental Health Index from the 36-item short-form health questionnaire and the 10-item Center for Epidemiologic Studies Depression Scale. Sociodemographic control variables included marital status, education level and employment status. RESULTS: A strong cross-sectional dose-response relationship between smoking and poor mental health was found at each wave [odds ratio (OR) 1.41, 95% confidence intervals (CI) 1.17-1.70 to OR 2.27, 95% CI 1.82-2.81]. Longitudinal results showed that women who smoked had 1.21 (95% CI 1.06-1.39) to 1.62 (95% CI 1.24-2.11) times higher odds of having poor mental health at subsequent waves. Women with poor mental health had 1.12 (95% CI 1.17-1.20) to 2.11 (95% CI 1.68-2.65) times higher odds of smoking at subsequent waves. These results held after adjusting for mental health history and smoking history and sociodemographic factors. Correlation analysis and structural equation modelling results were consistent in showing that both directions of the relationship were statistically significant. CONCLUSIONS: The association between poor mental health and smoking in young women appeared to be bi-directional.