Electroencephalogram (EEG) is one of the most important signals for diagnosis of Autism Spectrum Disorder (ASD). There are different challenges such as feature selection and the existence of artifacts in EEG signals. This article aims to present a robust method for early diagnosis of ASD from EEG signal. The study population consists of 34 children with ASD between 3–12 years and 11 healthy children in the same ranges of age. The proposed approach uses linear and nonlinear features such as Power Spectrum, Wavelet Transform, Fast Fourier Transform (FFT), Fractal Dimension, Correlation Dimension, Lyapunov Exponent, Entropy, Detrended Fluctuation Analysis and Synchronization Likelihood for describing the EEG signal. In addition Density Based Clustering is utilized for artifact removal and robustness. Besides, features selection is applied based on different criterions such as Mutual Information (MI), Information Gain (IG), Minimum-Redundancy Maximum-Relevancy (mRmR) and Genetic Algorithm (GA). Finally, the K-Nearest-Neighbor (KNN) and Support Vector Machines (SVM) classifiers are used for final decision. As a result, the investigation indicates that the classification accuracy of the approach using SVM is 90.57% while for KNN it is 72.77%. Moreover, the sensitivity of the proposed method is 99.91% for SVM and 91.96% for KNN. Also, experiments show that DFA, LE, Entropy and SL features have considerable influence in promoting the classification accuracy.