Being highly attentive to details can be a positive feature. However, for some individuals, perfectionism can lead to distress and is associated with many psychiatric disorders. Cognitive behavior therapy has been shown to yield many benefits for those experiencing problems with perfectionism, but the access to evidence-based care is limited. The current study investigated the efficacy of guided Internet-based Cognitive Behavior Therapy (ICBT) and predictors of treatment outcome. In total, 156 individuals were included and randomized to an eight-week treatment or wait-list control. Self-report measures of perfectionism, depression, anxiety, self-criticism, self-compassion, and quality of life were distributed during screening and at post-treatment. Intention-to-treat were used for all statistical analyses. Moderate to large between-group effect sizes were obtained for the primary outcome measures, Frost Multidimensional Perfectionism Scale, subscales Concerns over Mistakes and Personal Standards, Cohen's d = 0.68–1.00, 95% Confidence Interval (CI) [0.36–1.33], with 35 (44.9%) of the patients in treatment being improved. Predictors were also explored, but none were related to treatment outcome. In sum, guided ICBT can be helpful for addressing problems with clinical perfectionism, but research of its long-term benefits is warranted.