Purpose: The aims of the present study were to (a) examine the rate of social phobia among adults who stutter, (b) study the effects of speech restructuring treatment on social anxiety, and (c) study the effects on anxiety and stuttering of a cognitive-behavior therapy (CBT) package for social anxiety. Method: Thirty-two adults with chronic stuttering were randomly allocated to receive either speech restructuring following a CBT package for social anxiety or speech restructuring alone. Data were obtained on a variety of speech and psychological measures at pre-treatment, post-CBT, post-speech restructuring, and 12 months follow-up. Results: Sixty percent of our cohort were diagnosed with social phobia. Speech restructuring treatment alone had no impact on the social phobia of our cohort at 12 months follow-up. At follow-up, participants who had received CBT showed no social phobia and greater improvements than control participants on a range of psychological measures of anxiety and avoidance. However, the CBT package made no difference to the speech outcomes of those with social phobia. Conclusion: The CBT treatment was associated with significant and sustained improvements in psychological functioning but did not improve fluency.