The aim of the present study was to analyze resting-state brain activity in patients with Parkinson's disease (PD), a degenerative disorder of the nervous system. Magnetoencephalography (MEG) signals were recorded with a 151-channel whole-head radial gradiometer MEG system in 18 early-stage untreated PD patients and 20 age-matched control subjects. Artifact-free epochs of 4 s (1250 samples) were analyzed with Lempel-Ziv complexity (LZC), applying two- and three-symbol sequence conversion methods. The results showed that MEG signals from PD patients are less complex than control subjects' recordings. We found significant group differences (p-values <0.01) for the 10 major cortical areas analyzed (e.g., bilateral frontal, central, temporal, parietal, and occipital regions). In addition, using receiver-operating characteristic curves with a leave-one-out cross-validation procedure, a classification accuracy of 81.58% was obtained. In order to investigate the best combination of LZC results for classification purposes, a forward stepwise linear discriminant analysis with leave-one out cross-validation was employed. LZC results (three-symbol sequence conversion) from right parietal and temporal brain regions were automatically selected by the model. With this procedure, an accuracy of 84.21% (77.78% sensitivity, 90.0% specificity) was achieved. Our findings demonstrate the usefulness of LZC to detect an abnormal type of dynamics associated with PD.