Dietary guidelines around the world recommend increased intakes of fruits and non-starchy vegetables for the prevention of chronic diseases and possibly obesity. This study aimed to describe the association between body mass index (BMI) and habitual fruit and vegetable consumption in a large sample of 246,995 Australian adults aged 45 + year who had been recruited for the “45 and Up” cohort study. Fruit and vegetable intake was assessed using validated short questions, while weight and height were self-reported. Multinomial logistic regression was used, by sex, to assess the association between fruit and vegetable intake and BMI. Compared to the referent normal weight category (BMI 18.5 to 24.9), the odds ratio (OR) of being in the highest vegetable intake quartile was 1.09 (95% confidence interval (CI) 1.04–1.14) for overweight women (BMI 25.0–29.9) and 1.18 (95% CI 1.12–1.24) for obese women. The association was in the opposite direction for fruit for overweight (OR 0.85; 95% CI 0.80–0.90) and obese women (OR 0.75; 95% CI 0.69–0.80). Obese and overweight women had higher odds of being in the highest intake quartile for combined fruit and vegetable intake, and were more likely to meet the “2 and 5” target or to have five or more serves of fruit and vegetables per day. In contrast, overweight men were less likely to be in high intake quartiles and less likely to meet recommended target of 5 per day, but there was no consistent relationship between obesity and fruit and vegetable intake. Underweight women and underweight men were less likely to be in the highest intake quartiles or to meet the recommended targets. These data suggest that improving adherence to dietary targets for fruit and vegetables may be a dietary strategy to overcome overweight among men, but that overweight and obese women are already adhering to these targets. The association between fruit and vegetable intake and underweight in adults suggests that improving fruit and vegetables intakes are important for the overall dietary patterns of people in this group.