Given the subjective nature of conventional diagnostic methods for post-traumatic stress disorder (PTSD), an objectively measurable biomarker is highly desirable; especially to clinicians and researchers. Macroscopic neural circuits measured using magnetoencephalography (MEG) has previously been shown to be indicative of the PTSD phenotype and severity. In the present study, we employed a machine learning-based classification framework using MEG neural synchrony to distinguish combat-related PTSD from trauma-exposed controls. Support vector machine (SVM) was used as the core classification algorithm. A recursive random forest feature selection step was directly incorporated in the nested SVM cross validation process (CV-SVM-rRF-FS) for identifying the most important features for PTSD classification. For the five frequency bands tested, the CV-SVM-rRF-FS analysis selected the minimum numbers of edges per frequency that could serve as a PTSD signature and be used as the basis for SVM modelling. Many of the selected edges have been reported previously to be core in PTSD pathophysiology, with frequency-specific patterns also observed. Furthermore, the independent partial least squares discriminant analysis suggested low bias in the machine learning process. The final SVM models built with selected features showed excellent PTSD classification performance (area-under-curve value up to 0.9). Testament to its robustness when distinguishing individuals from a heavily traumatised control group, these developments for a classification model for PTSD also provide a comprehensive machine learning-based computational framework for classifying other mental health challenges using MEG connectome profiles.