Complexity measures have been enormously used in schizophrenia patients to estimate brain dynamics. However, the conflicting results in terms of both increased and reduced complexity values have been reported in these studies depending on the patients' clinical status or symptom severity or medication and age status. The objective of this study is to investigate the nonlinear brain dynamics of chronic and medicated schizophrenia patients using distinct complexity estimators. EEG data were collected from 22 relaxed eyes-closed patients and age-matched healthy controls. A single-trial EEG series of 2 min was partitioned into identical epochs of 20 s intervals. The EEG complexity of participants were investigated and compared using approximate entropy (ApEn), Shannon entropy (ShEn), Kolmogorov complexity (KC) and Lempel-Ziv complexity (LZC). Lower complexity values were obtained in schizophrenia patients. The most significant complexity differences between patients and controls were obtained in especially left frontal (F3) and parietal (P3) regions of the brain when all complexity measures were applied individually. Significantly, we found that KC was more sensitive for detecting EEG complexity of patients than other estimators in all investigated brain regions. Moreover, significant inter-hemispheric complexity differences were found in the frontal and parietal areas of schizophrenics' brain. Our findings demonstrate that the utilizing of sensitive complexity estimators to analyze brain dynamics of patients might be a useful discriminative tool for diagnostic purposes. Therefore, we expect that nonlinear analysis will give us deeper understanding of schizophrenics' brain.