People suffer from sleep disorders caused by work-related stress, irregular lifestyle or mental health problems. Therefore, development of effective tools to diagnose sleep disorders is important. Recently, to analyze biomedical signals Information Theory is exploited. We propose efficient classification method of sleep anomalies by applying entropy estimating algorithms to encoded ECGs signals coming from patients suffering from Sleep-Related Breathing Disorders (SRBD).First, ECGs were discretized using the encoding method which captures the biosignals variability. It takes into account oscillations of ECG measurements around signals averages. Next, to estimate entropy of encoded signals Lempel-Ziv complexity algorithm (LZ) which measures patterns generation rate was applied. Then, optimal encoding parameters, which allow distinguishing normal versus abnormal events during sleep with high sensitivity and specificity were determined numerically. Simultaneously, subjects' states were identified using acoustic signal of breathing recorded in the same period during sleep.Random sequences show normalized LZ close to 1 while for more regular sequences it is closer to 0. Our calculations show that SRBDs have normalized LZ around 0.32 (on average), while control group has complexity around 0.85. The results obtained to public database are similar, i.e. LZ for SRBDs around 0.48 and for control group 0.7. These show that signals within the control group are more random whereas for the SRBD group ECGs are more deterministic. This finding remained valid for both signals acquired during the whole duration of experiment, and when shorter time intervals were considered. Proposed classifier provided sleep disorders diagnostics with a sensitivity of 93.75 and specificity of 73.00%. To validate our method we have considered also different variants as a training and as testing sets. In all cases, the optimal encoding parameter, sensitivity and specificity values were similar to our results above.Our pilot study suggests that LZ based algorithm could be used as a clinical tool to classify sleep disorders since the LZ complexities for SRBD positives versus healthy individuals show a significant difference. Moreover, normalized LZ complexity changes are related to the snoring level. This study also indicates that LZ technique is able to detect sleep abnormalities in early disorders stage.