Background: The present study aimed to investigate the association between vegetable consumption, in total as well as per type/category, and 10-year type-2 diabetes mellitus (T2DM) incidence. Methods: The ATTICA study was conducted during 2001–2012 in 3042 apparently healthy adults living in Athens area, Greece. A detailed biochemical, clinical, and lifestyle evaluation was performed; vegetable consumption (total, per type) was evaluated through a validated semi-quantitative food frequency questionnaire. After excluding those with no complete information of diabetes status or those lost at the 10-year follow-up, data from 1485 participants were used for the current analysis. Results: After adjusting for several participants' characteristics, including overall dietary habits, it was observed that participants consuming at least 4 servings/day of vegetables had a 0.42-times lower risk of developing T2DM (hazard ratio [HR] = 0.42; 95% confidence interval [CI] = 0.29–0.61); the benefits of consumption were greater in women (HR = 0.29; 95% CI = 0.16–0.53) compared to men (HR = 0.56; 95% CI = 0.34–0.92). Only 33% of the sample consumed vegetables 4 servings/day. The most significant associations were observed for allium vegetables in women and for red/orange/yellow vegetables, as well as for legumes in men. Conclusions: The intake of at least 4 servings/day of vegetables was associated with a considerably reduced risk of T2DM, independently of other dietary habits; underlying the need for further elaboration of current dietary recommendations at the population level.