This study was designed to analyze the magnetoencephalogram (MEG) background activity from 20 patients with probable Alzheimer's disease (AD) and 21 control subjects by using two nonlinear methods: sample entropy (SampEn), and Lempel-Ziv complexity (LZC). The former quantifies the signal regularity, and the latter is a complexity measure. The signals were acquired with a 148-channel whole-head magnetometer placed in a magnetically shielded room. Our results show that MEG recordings are less complex and more regular in patients with AD than in control subjects. Significant differences between both groups were found in 16 MEG channels with SampEn and in 134 with LZC (p < 0.01, Student's t test with Bonferroni's correction). Using receiver operating characteristic curves with a leave-one-out cross-validation procedure, accuracies of 70.73 and 78.05% were reached with SampEn and LZC, respectively. Additionally, we wanted to assess whether both nonlinear methods and an adaptive-network-based fuzzy interference system (ANFIS) could improve AD diagnosis. With this classifier, an accuracy of 85.37% was achieved. Our findings suggest the usefulness of our methodology to increase our insight into AD.