Approximately 30 percent of U.S. veterans deployed during the Gulf War (1990–1991) have been diagnosed with Gulf War Illness (GWI), a chronic multi-symptom disorder without widely available specific treatments. We investigated whether the consumption of Concord grape juice (CGJ), rich in anti-inflammatory flavonoids, would be tolerated and safe in individuals with GWI and explored improvement in cognitive function and fatigue. Thirty-six veterans with GWI enrolled in a 24-week randomized, double-blind, Phase I/IIA clinical trial to explore safety, tolerability, and feasibility of 16 ounces daily of commercially available CGJ compared to placebo. Participants completed neurocognitive tests and self-reported surveys at baseline, 12 and 24 weeks. Thirty-one participants (86%) completed the study; no dropouts were related to side effects. Thirty participants (83%) documented ≥80% adherence. There were no statistically significant unadjusted differences between CGJ and placebo groups in change in efficacy measures from baseline to endpoint. We employed general linear regression models controlling for baseline differences between groups which indicated statistically significant improvement in the Halstead Category Test–Russell Revised Version (RCAT) at endpoint in the CGJ group compared to placebo (8.4 points, p = 0.04). Other measures of cognitive functioning did not indicate significant improvements in the adjusted analyses (p-values: 0.09–0.32), nor did the fatigue variable (p = 0.67). CGJ was safe and well-tolerated by veterans with GWI. Our data suggest high tolerability and potential benefit from CGJ in veterans with GWI and can be used to inform future studies of efficacy.