Mild traumatic brain injury (mTBI) is a common injury for service members in recent military conflicts. There is insufficient evidence of how best to treat the consequences of mTBI. In a randomized, clinical trial, we evaluated the efficacy of telephone-delivered problem-solving treatment (PST) on psychological and physical symptoms in 356 post-deployment active duty service members from Joint Base Lewis McChord, Washington, and Fort Bragg, North Carolina. Members with medically confirmed mTBI sustained during deployment to Iraq and Afghanistan within the previous 24 months received PST or education-only (EO) interventions. The PST group received up to 12 biweekly telephone calls from a counselor for subject-selected problems. Both groups received 12 educational brochures describing common mTBI and post-deployment problems, with follow-up for all at 6 months (end of PST), and at 12 months. At 6 months, the PST group significantly improved on a measure of psychological distress (Brief Symptom Inventory; BSI-18) compared to the EO group (p = 0.005), but not on post-concussion symptoms (Rivermead Post-Concussion Symptoms Questionnaire [RPQ]; p = 0.19), the two primary endpoints. However, these effects did not persist at 12-month follow-up (BSI, p = 0.54; RPQ, p = 0.45). The PST group also had significant short-term improvement on secondary endpoints, including sleep (p = 0.01), depression (p = 0.03), post-traumatic stress disorder (p = 0.04), and physical functioning (p = 0.03). Participants preferred PST overEO(p < 0.001). Telephone-delivered PST appears to be a well-accepted treatment that offers promise for reducing psychological distress after combat-related mTBI and could be a useful adjunct treatment post-mTBI. Further studies are required to determine how to sustain its effects. (Trial registration: ClinicalTrials.gov Identifier: NCT01387490 https://clinicaltrials. gov)