The diagnosis of social anxiety disorder (SAD) is of great consequence not only due to its impacts on the individual and society but also the expenditures to the national health systems. There is yet a deficiency of objective neurophysiological information to assist the present clinical SAD diagnosis. The main objective of this study is to analyze the electroencephalogram (EEG) complexity of 88 SAD subjects, subdivided into 4 balanced groups (22 severe, 22 moderate, 22 mild, and 22 healthy controls (HCs) using Fuzzy Entropy measure (FE) and machine learning algorithms. In addition, this study aimed at designing a computer-aided diagnosis system to identify the severity of SAD (severe, moderate, mild, and HC) in different EEG frequency bands (delta, theta, alpha, and beta). The experimental results showed that among the HC and the three considered levels of SAD, SAD patients in fast-waves exhibited significantly less FE values in resting-state compared with HCs (p ≤0.05 ). The EEG complexity analysis showed a discriminatory neuronal activity over the frontoparietal and occipital regions between SAD patients and HCs. Additionally, the FE values measured in the resting-state were positively correlated with Social Interaction Anxiety Scale (SIAS) scores in fast-waves (beta and alpha), indicating that the regional FE measures are putative biomarkers in assessing the clinical symptoms of SAD. Also, the classification results demonstrated that the proposed method outperformed the state of the art methods with an accuracy of 86.93 , sensitivity of 92.46, and specificity of 95.32 with the Naive Bayes (NB) classifier. This study emphasizes the viability of quantitative FE measures and the specific combinations involving the chosen classifiers could be considered as an alternative biomarker for future clinical SAD recognition. © 2013 IEEE.