The influence of fruit and vegetable consumption on semen quality by reducing oxidative stress is inconsistent. Thus, the association between the consumption of these products, antioxidant status, and semen quality was investigated in 90 men aged 18–40. The consumption of fruit and vegetables was collected using the 3-day food record method. Antioxidant status: total antioxidant capacity in semen (TAC-s) and blood (TAC-b), blood superoxide dismutase (SOD-b), glutathione reductase (GR-b), glutathione peroxidase (GPx-b), catalase (CAT-b) activity, and malondialdehyde concentration in blood (MDA-b) were measured. Sperm concentration, leukocytes in the ejaculate, vitality, motility, and sperm morphology were examined using computer-aided semen analysis (CASA). The consumption of fruit and vegetables was positively correlated with sperm concentration, vitality, motility, TAC-s, TAC-b, and SOD-b activity. The TAC-s and TAC-b were positively related to motility, TAC-s was inversely correlated with sperm tail defects. The SOD-b activity was positively correlated with vitality, motility, sperm morphology, and inversely with sperm tail defects and leukocytes in the ejaculate. Compared to the men in the first quartile of fruit and vegetable consumption (<318 g/day), those in the highest quartile (>734 g/day) had the highest sperm concentration, vitality, motility, TAC-s, TAC-b, GPx-b activity, and the lowest MDA-b concentration (based on multivariate regression models). A high consumption of fruit and vegetables may positively influence selected sperm quality parameters by improving the antioxidant status of semen and blood.