With the release of the Next Generation Science Standards (NGSS), assessing K–12 science teachers’ self-efficacy in Computational Thinking (CT) is an important research gap to study. Bandura defines self-efficacy as awareness of the individual’s potential and capabilities to accomplish a goal. Teaching efficacy beliefs is a significant identifier of teachers’ performance and motivation in teaching the specific content successfully; however, K–12 science teachers’ CT teaching efficacy beliefs are rarely discussed. Participating preservice elementary teachers (PSET) were enrolled in an undergraduate elementary science teaching methods course during the spring and summer 2018 semesters in a southwestern state university. We administered a CT teaching efficacy beliefs survey at the beginning and end of the related unit (i.e., the intervention). During the intervention, the PSET followed the CT practices by building educational robots, coding visual block-based programs, and solving puzzles in the video game “Zoombinis.” In this paper, we report the impact of the intervention on teaching efficacy beliefs of PSET. We used SPSS software to analyze our quantitative results. We performed paired samples t-test for the two teaching efficacy beliefs subscales, Personal Computational Thinking Teaching Efficacy (PCTTE) and Computational Thinking Teaching Outcome Expectancy (CTTOE), to measure if there is a significant difference in teaching efficacy beliefs. Our research findings suggest that introducing CT increases PSET CT teaching efficacy beliefs. Furthermore, based on the results of our exploratory research with PSET, we propose implications of the study for K–12 CT teaching efficacy beliefs and CT education research.