The first aim of the study was to analyze whether reading fluency and self-efficacy of reading fluency (SE-rf) are malleable for children (Grades 3–5) with deficits in fluent reading via a 12-week special education program targeting both reading fluency and the sources of SE-rf (SE-program). The second aim was to investigate whether changes in SE-rf are related to changes in reading fluency. The SE-program (n = 40) was contrasted with the SKILL-program (n = 42) providing training solely in reading fluency. The groups showed equal improvements in reading fluency. Positive change in SE-rf emerged only in the SE-group, and this change was associated with changes in fluency, but the association depended on the reading measure. The findings indicate that a reading fluency intervention supporting self-efficacy by providing concrete feedback and helping children to perceive their progress can yield positive changes in self-efficacy. More research is needed on the variability in intervention responsiveness.