Diagnosis of mild traumatic brain injuries (TBIs) has been difficult because of the absence of obvious focal brain lesions, using conventional computed tomography (CT) or magnetic resonance imaging (MRI) scans, in a large percentage of TBIs. One useful measure that can characterize potential tissue and neural network damage objectively is Lempel-Ziv complexity (LZC) applied to magnetoencephalography (MEG) signals. LZC is a model-independent estimator of system complexity that estimates the number of different patterns in a sequence. We hypothesized that because of the potential network damage, TBIs would show a reduced level of complexity in regions that are impaired. We included 18 healthy controls and 18 military veterans with TBI in the study. Resting state MEG data were acquired, and the LZCs were analyzed across the whole brain. Our results indicated reduced complexity in multiple brain areas in TBI patients relative to the healthy controls. In addition, we detected several neuropsychological measures associated with motor responses, visual perception, and memory, correlated with LZC, which likely explains some of the cognitive deficits in TBI patients.