Objective. Post-traumatic stress disorder (PTSD) is highly heterogeneous, and identification of quantifiable biomarkers that could pave the way for targeted treatment remains a challenge. Most previous EEG studies on PTSD have been limited to specific handpicked features, and their findings have been highly variable and inconsistent. Therefore, to disentangle the role of promising EEG biomarkers, we developed a machine learning framework to investigate a wide range of commonly used EEG biomarkers in order to identify which features or combinations of features are capable of characterizing PTSD and potential subtypes. Approach. We recorded five minutes of eyes-closed and five minutes of eyes-open resting-state EEG from 202 combat-exposed veterans (53% with probable PTSD and 47% combat-exposed controls). Multiple spectral, temporal, and connectivity features were computed and logistic regression, random forest, and support vector machines with feature selection methods were employed to classify PTSD. To obtain robust results, repeated two-layer cross-validation was utilized to test on an entirely unseen test set. Main results. Our classifiers obtained a balanced test accuracy of up to 62.9% for predicting PTSD patients. In addition, we identified two subtypes within PTSD: one where EEG patterns were similar to those of the combat-exposed controls, and another that were characterized by increased global functional connectivity. Our classifier obtained a balanced test accuracy of 79.4% when classifying this PTSD subtype from controls, a clear improvement compared to predicting the whole PTSD group. Interestingly, alpha connectivity in the dorsal and ventral attention network was particularly important for the prediction, and these connections were positively correlated with arousal symptom scores, a central symptom cluster of PTSD. Significance. Taken together, the novel framework presented here demonstrates how unsupervised subtyping can delineate heterogeneity and improve machine learning prediction of PTSD, and may pave the way for better identification of quantifiable biomarkers.