Although cognitive behavioral interventions improve attitudes toward mental health treatment and reduce stigma, little is known about which types of attitudes change, or how this change occurs. Active duty soldiers with PTSD (N = 162) were randomized to 10 sessions of exposure therapy or a waitlist. Soldiers were assessed for PTSD and completed measures of stigma and attitudes towards mental health services before randomization and after 5- and 10- sessions of therapy. At post-treatment, soldiers in exposure therapy demonstrated significant improvements in openness to talking about mental health problems and concerns about what others may think if they knew they were seeking mental health treatment, relative to those in the waitlist. There were significant indirect effects from treatment to changes in stigma and attitudes towards mental health treatment through changes in PTSD symptoms at post-treatment. There was also a significant indirect effect from treatment to changes in stigma at post-treatment through changes in attitudes towards mental health treatment at mid-treatment, suggesting attitude change may occur first. Baseline characteristics did not moderate treatment's change in stigma or attitudes. Improvements in PTSD symptoms and positive changes in attitudes towards mental health treatment appear to separately predict later reductions in stigma.