Posttraumatic stress disorder (PTSD) is associated with a reduced ratio of naïve cytotoxic T lymphocytes, an increased ratio of memory cytotoxic T lymphocytes, and a reduced proportion of FoxP3+ regulatory T lymphocytes. This study investigated whether these immunological alterations are reversible through an evidence-based psychotherapeutic treatment. Therefore, 34 individuals with PTSD were randomly assigned to either a treatment condition of 12 sessions narrative exposure therapy (NET) or a waitlist control (WLC) group. PTSD symptoms were significantly reduced in the NET group, but not in the WLC group, four months post-therapy (effect size: Hedges' g = −1.61). One year after therapy, PTSD symptoms were improved even further in the NET group compared to baseline (Hedges' g = −1.96). This symptom improvement was mirrored in an increase in the originally reduced proportion of regulatory T cells (Tregs) in the NET group at the one-year follow-up, when comparing subgroups matched for baseline Treg numbers. However, no changes were found for the initially reduced proportion of CD45RA+CCR7+ naïve T lymphocytes. In conclusion, NET was effective in reducing trauma-related PTSD symptoms and had a positive effect on the proportion of Tregs cells, thus demonstrating an effect of psychotherapy on an immunological level. Yet, the shift in the proportion of naïve and memory T lymphocytes in individuals with PTSD, discussed in the literature as a correlate of premature immunosenescence, was not reversible and thus might render these patients permanently more susceptible to infectious diseases.