Among the different therapeutic alternatives for post-traumatic stress disorder (PTSD), Trauma-Focused Cognitive-Behavioral Therapy (TF-CBT) and Eye Movement Desensitization and Reprocessing (EMDR) Therapy have shown promising results in helping patients cope with PTSD symptoms. However, given the different theoretical and methodological substrate of TF-CBT and EMDR, a potentially different impact on the brain for the two interventions could be hypothesized, as well as an interaction between trauma-specific PTSD symptomatology and response to a given psychotherapy. In this study, we monitored psychological and spontaneous functional connectivity fMRI patterns in two groups of PTSD patients who suffered by the same traumatic event (i.e., natural disaster), before and after a cycle of psychotherapy sessions based on TF-CBT and EMDR. Thirty-seven (37) PTSD patients were enrolled from a larger sample of people exposed to a single, acute psychological stress (i.e., 2002 earthquake in San Giuliano di Puglia, Italy). Patients were randomly assigned to TF-CBT (n = 14) or EMDR (n = 17) psychotherapy. Clinical assessment was performed using the Clinician-Administered PTSD Scale (CAPS), the Davidson Trauma Scale (DTS) and the Work and Social Adjustment Scale (WSAS), both at baseline and after treatment. All patients underwent a fMRI data acquisition session before and after treatment, aimed at characterizing their functional connectivity (FC) profile at rest, as well as potential connectivity changes associated with the clinical impact of psychotherapy. Both EMDR and TF-CBT induced statistically significant changes in clinical scores, with no difference in the clinical impact of the two treatments. Specific changes in FC correlated with the improvement at the different clinical scores, and differently for EMDR and TF-CBT. However, a similarity in the connectivity changes associated with changes in CAPS in both groups was also observed. Specifically, changes at CAPS in the entire sample correlated with an (i) increase in connectivity between the bilateral superior medial frontal gyrus and right temporal pole, and a (ii) decrease in connectivity between left cuneus and left temporal pole. Results point to a similar, beneficial psychological impact of EMDR and TF-CBT for treatment of natural-disaster PTSD patients. Neuroimaging data suggest a similar neurophysiological substrate for clinical improvement following EMDR and TF-CBT, involving changes affecting bilateral temporal pole connectivity.