Patients with prolonged disorders of consciousness (PDOC) are often unable to communicate their state of consciousness. Determining the latter is essential for the patient's care and prospects of recovery. Auditory stimulation in combination with neural recordings has recently been highlighted as a promising technique towards objective estimation of conscious awareness. Here, we investigate the potential of statistically defined acoustic stimuli to elicit EEG responses suitable for distinguishing between 5 subject groups, ranging from unconscious to responding.We presented naturalistic textures to listeners, which changed their statistics unexpectedly. Active listeners indicated the change by button press, while all other groups (passive, asleep, minimally conscious (MCS), unresponsive wakefulness (UWS)) listened passively. We quantified the evoked potential at onset and change in statistics and their descriptional complexity (Lempel-Ziv complexity (LZC)).On the group level, evoked potentials can separate patients from healthy controls, but fail to differentiate between the patient groups. LZC reliably differentiates between individual patients, when compared with the classical behavioral scale.In summary, EEG signal complexity during changes of complex acoustic stimuli provides an objective criterion for distinguishing states of consciousness in clinical patients. These results suggests a path toward a cost-effective tool to choose appropriate treatments for non-responsive PDOC patients.