Previously, a lower risk of colorectal cancer was observed with fruit and vegetable consumption in the European Prospective Investigation into Cancer and Nutrition within a follow-up period of 9 years which was not fully supported by a recent meta-analysis. Therefore, we were interested in the relation with extended follow-up, also focusing on single subtypes and a variety of intake of fruit and vegetables. Fruit and vegetable consumption was assessed at baseline. After an average of 13 years of follow-up, 3,370 participants were diagnosed with colon or rectal cancer. Diet diversity scores were constructed to quantify variety in fruit and vegetable consumption. A lower risk of colon cancer was observed with higher self-reported consumption of fruit and vegetable combined (HR Q4 vs. Q1 0.87, 95% CI 0.75–1.01, p for trend 0.02), but no consistent association was observed for separate consumption of fruits and vegetables. No associations with risk of rectal cancer were observed. The few observed associations for some fruit and vegetable subtypes with colon cancer risk may have been due to chance. Variety in consumption of fruits and vegetables was not associated with a lower risk of colon or rectal cancer. Although a lower risk of colon cancer is suggested with high consumption of fruit and vegetables, this study does not support a clear inverse association between fruit and vegetable consumption and colon or rectal cancer beyond a follow-up of more than 10 years. Attenuation of the risk estimates from dietary changes over time cannot be excluded, but appears unlikely.