Epigenetic mechanisms play a role in the detrimental effects of traumatic stress and the development of post-traumatic stress disorder (PTSD). However, it is unknown whether successful treatment of PTSD restores these epigenetic marks. This study investigated longitudinal changes of blood-based genome-wide DNA methylation levels in relation to trauma-focused psychotherapy for PTSD in soldiers that obtained remission (N = 21), non-remitted PTSD patients (N = 23), and trauma-exposed military controls (N = 23). In an independent prospective cohort, we then examined whether these DMRs were also relevant for the development of deployment-related PTSD (N = 85). Successful treatment of PTSD was accompanied by significant changes in DNA methylation at 12 differentially methylated regions (DMRs) in the genes: APOB, MUC4, EDN2, ZFP57, GPX6, CFAP45, AFF3, TP73, UBCLP1, RPL13P, and two intergenic regions (p values < 0.0001 were confirmed using permutation and sensitivity analyses). Of the 12 DMRs related to PTSD symptom reduction, consistent prospective evidence was found for ZFP57 methylation changes related to changing PTSD symptoms (B = −0.84, t = −2.49, p = 0.014). Increasing ZFP57 methylation related to PTSD symptom reduction was present over and above the relation with symptoms, suggesting that psychological treatments exert biological effects independent of symptom reduction. Together, these data provide longitudinal evidence that ZFP57 methylation is involved in both the development and successful treatment of deployment-related PTSD. This study is a first step to disentangle the interaction between psychological and biological systems to identify genomic regions relevant for the etiology and treatment of stress-related disorders such as PTSD.