The depth of anesthesia estimation has been of great interest in recent decades. In this paper, we present a new methodology to quantify the levels of consciousness. Our algorithm takes advantage of the fractal and self-similarity properties of the electroencephalogram (EEG) signal. We have studied the effect of anesthetic agents on the rate of the signal fluctuations. By translating these fluctuations with detrended fluctuation analysis (DFA) algorithm to fractal exponent, we could describe the dynamics of brain during anesthesia. We found the optimum fractal-scaling exponent by selecting the best domain of box sizes, which have meaningful changes with different depth of anesthesia. Experimental results confirm that the optimal fractal-scaling exponent on the raw EEG data can clearly discriminate between awake to moderate and deep anesthesia levels and have robust relation with the well-known depth of anesthesia index (BIS). When the patient's cerebral states change from awake to moderate and deep anesthesia, the fractal-scaling exponent increases from 0.8 to 2 approximately. Moreover, our new algorithm significantly reduces computational complexity and produces faster reaction to transients in patients’ consciousness levels compared to other algorithms and technologies.