The information processing capability of the brain decreases during unconscious states. Capturing this decrease during anesthesia-induced unconsciousness has been attempted using standard spectral analyses as these correlate relatively well with breakdowns in corticothalamic networks. Much of this work has involved the use of propofol to perturb brain activity, as it is one of the most widely used anesthetics for routine surgical anesthesia. Propofol administration alone produces EEG spectral characteristics similar to most hypnotics; however, inter-individual and drug variation render spectral measures inconsistent. Complexity measures of EEG signals could offer better measures to distinguish brain states, because brain activity exhibits nonlinear behavior at several scales during transitions of consciousness. We tested the potential of complexity analyses from nonlinear dynamics to identify loss and recovery of consciousness at clinically relevant timepoints. Patients undergoing propofol general anesthesia for various surgical procedures were identified as having changes in states of consciousness by the loss and recovery of response to verbal stimuli after induction and upon cessation of anesthesia, respectively. We demonstrate that nonlinear dynamics analyses showed more significant differences between consciousness states than spectral measures. Notably, attractors in conscious and anesthesia-induced unconscious states exhibited significantly different shapes. These shapes have implications for network connectivity, information processing, and the total number of states available to the brain at these different levels. They also reflect some of our general understanding of the network effects of consciousness in a way that spectral measures cannot. Thus, complexity measures could provide a universal means for reliably capturing depth of consciousness based on EEG changes at the beginning and end of anesthesia administration.