Post-traumatic stress disorder (PTSD) is a mental health injury characterised by re-experiencing, avoidance, numbing and hyperarousal. Whilst the aetiology of the disorder is relatively well understood, there is debate about the prevalence of cognitive sequelae that manifest in PTSD. In particular, there are conflicting reports about deficits in executive function and mental flexibility. Even less is known about the neural changes that underlie such deficits. Here, we used magnetoencephalography to study differences in functional connectivity during a mental flexibility task in combat-related PTSD (all males, mean age = 37.4, n = 18) versus a military control (all males, mean age = 33.05, n = 19) group. We observed large-scale increases in theta connectivity in the PTSD group compared to controls. The PTSD group performance was compromised in the more attentionally-demanding task and this was characterised by 'late-stage' theta hyperconnectivity, concentrated in network connections involving right parietal cortex. Furthermore, we observed significant correlations with the connectivity strength in this region with a number of cognitive-behavioural outcomes, including measures of attention, depression and anxiety. These findings suggest atypical coordination of neural synchronisation in large scale networks contributes to deficits in mental flexibility for PTSD populations in timed, attentionally-demanding tasks, and this propensity toward network hyperconnectivity may play a more general role in the cognitive sequelae evident in this disorder.