Extensive evidence suggests the feasibility of lie detection using electroencephalograms (EEGs). However, it is largely unknown whether there are any differences in the nonlinear features of EEGs between guilty and innocent subjects. In this study, we proposed a complexity-based method to distinguish lying from truth telling. A total of 35 participants were randomly divided into two groups, and their EEG signals were recorded with 14 electrodes. Averages for sequential sets of five trials were first calculated for the probe responses within each subject. Next, a common wavelet entropy (WE) measure and an improved one were used to quantify complexity from each five-trial average. The results show that for both measures, the WE values in the guilty subjects are statistically lower than those in the innocent subjects for most of the 14 electrodes. More importantly, using the improved measure, the difference in WE between the two groups of subjects significantly increases for 11 brain regions compared with the values from the common measure. Finally, the highest balanced classification accuracy, 89.64%, is achieved when using the combined WE feature vector in five brain regions from the sites of Pz, P3, C4, Cz, and C3. Our findings indicate that the lying task elicits a more ordered brain activity in some specific brain regions than the task of telling the truth. This study not only demonstrates that improved WE measurements could be a powerful quantitative index for detecting lying but also sheds light on the brain mechanisms underlying deceptive behaviors.