Around 200,000 veterans of the 1991 Gulf War (GW) suffer from GW illness (GWI), which is characterized by deficits in cognitive, emotion, perception and nociception domains. Previous studies have associated GWI with exposure to neurotoxic chemicals which impair the cholinergic system. Recently, an fMRI time-series signal complexity metric, multi-scale entropy (MSE) has been proposed as a potential biomarker of abnormal neural activity in brain disorders. In this study, we examined 23 GWI patients and 30 age-matched controls with resting state fMRI. GWI veterans exhibited abnormally increased MSE all across cerebellum, implicating cholinergic damage of cerebellum as a mechanism underlying GWI.