The inclusion of computational thinking (CT) into science curricula has advocated implementing a computationally rich science learning environment where students learn science via building models in a computer programming platform. Such an approach may influence teachers' self-efficacy for teaching science which may also be associated with their self-efficacy for teaching CT. Framed using Bandura's Social Cognitive Theory, this study investigated the changes and sources of changes of Indonesian teachers' self-efficacy for teaching science and CT and looking at whether the two constructs are correlated. A total of eleven Indonesian middle school science teachers (seven in-service and four pre-service) participated in a CT-integrated science instruction workshop. They then implemented the curriculum they learned and obtained from the workshop in their classrooms. The teachers took questionnaires on science and CT teaching efficacy beliefs four times: before and after the workshop and before and after they taught. As a follow-up, interviews and writing reflections were collected after they took the instruments. Skillings-Mack and repeated-measures correlation tests were run on the quantitative data, and the qualitative data were analyzed thematically. Results from quantitative analyses revealed a pattern of increasing teachers' self-efficacy for teaching science and CT in a computationally rich environment over the administrations of the instrument. Thematic analysis showed three sources of teachers' self-efficacy: computer programming experience, students' interests, and teaching repetition and field experience. This study calls attention to the importance of providing experience for teachers to teach science in a computationally rich environment, whether through professional development or teacher education programs.