Evidence supports exercise as an intervention for many mental health concerns; however, randomized controlled investigations of the efficacy of different exercise modalities and predictors of change are lacking. The purposes of the current trial were to: (1) quantify the effects of aerobic exercise and resistance training on anxiety-related disorder (including anxiety disorders, obsessive-compulsive disorder, and posttraumatic stress disorder) status, symptoms, and constructs, (2) evaluate whether both modalities of exercise were equivalent, and (3) to determine whether exercise enjoyment and physical fitness are associated with symptom reduction. A total of 48 individuals with anxiety-related disorders were randomized to aerobic exercise, resistance training, or a waitlist. Symptoms of anxiety-related disorders, related constructs, and exercise enjoyment were assessed at pre-intervention and weekly during the 4-week intervention. Participants were further assessed 1-week and 1-month post-intervention. Both exercise modalities were efficacious in improving disorder status. As well, aerobic exercise improved general psychological distress and anxiety, while resistance training improved disorder-specific symptoms, anxiety sensitivity, distress tolerance, and intolerance of uncertainty. Physical fitness predicted reductions in general psychological distress for both types of exercise and reductions in stress for aerobic exercise. Results highlight the efficacy of different exercise modalities in uniquely addressing anxiety-related disorder symptoms and constructs.