An accurate diagnosis of the disorder of consciousness (DOC) is essential for generating tailored treatment programs. Accurately diagnosing patients with a vegetative state (VS) and patients in a minimally conscious state (MCS), however, might be very complicated, reaching a misdiagnosis of approximately 40% if clinical scales are not carefully administered and continuously repeated. To improve diagnostic accuracy for those patients, tools such as electroencephalography (EEG) might be used in the clinical setting. Many linear indices have been developed to improve the diagnosis in DOC patients, such as spectral power in different EEG frequency bands, spectral power ratios between these bands, and the difference between eyes-closed and eyes-open conditions (i.e. alpha-blocking). On the other hand, much less has been explored using nonlinear approaches. Therefore, in this work, we aim to discriminate between MCS and VS groups using a nonlinear method called Higuchi’s Fractal Dimension (HFD) and show that HFD is more sensitive than linear methods based on spectral power methods. For the sake of completeness, HFD has also been tested against another nonlinear approach widely used in EEG research, the Entropy (E). To our knowledge, this is the first time that HFD has been used in EEG data at rest to discriminate between MCS and VS patients. A comparison of Bayes factors found that differences between MCS and VS were 11 times more likely to be detected using HFD than the best performing linear method tested and almost 32 times with respect to the E. Machine learning has also been tested for HFD, reaching an accuracy of 88.6% in discriminating among VS, MCS and healthy controls. Furthermore, correlation analysis showed that HFD was more robust to outliers than spectral power methods, showing a clear positive correlation between the HFD and Coma Recovery Scale-Revised (CRS-R) values. In conclusion, our work suggests that HFD could be used as a sensitive marker to discriminate between MCS and VS patients and help decrease misdiagnosis in clinical practice when combined with commonly used clinical scales.