This study investigates the relationship between diet quality and weight gain in young women. Young women (n = 4,287, with 1,356 women identified as plausible subsample aged 27.6 ± 1.5 years at baseline) sampled from the Australian Longitudinal Study on Women's Health study completed food frequency questionnaires in 2003, which were used to evaluate diet quality using three indices: Australian Recommended Food Score (ARFS), Australian Diet Quality Index (Aus-DQI), and Fruit and Vegetable Index (FAVI). Weight was self-reported in 2003 and 2009. Multivariate linear regression was used to examine the association between tertiles of each diet quality index and weight change from 2003 to 2009. The ARFS and FAVI were significant predictors of 6-year weight change in this group of young women, while Aus-DQI did not predict weight change (P > 0.05). In the fully adjusted model, those who were in the top tertile of the ARFS significantly gained lower weight gain compared with the lower tertile for the plausible TEI sub-sample (β = -1.6 kg (95% CI: -2.67 to -0.56), P = 0.003). In the fully adjustment model, young women were classified in the highest FAVI tertile and gained significantly less weight than those in the lowest tertile for the plausible TEI (β = -1.6 kg (95% CI: -2.4 to -0.3) P = 0.01). In conclusion, overall diet quality measured by the ARFS and the frequency and variety of fruit and vegetable consumption may predict long-term weight gain in young women. Therefore, health promotion programs encouraging frequent consumption of a wide variety of fruits and vegetables are warranted.