Sporadic efforts have been made to introduce computational thinking methods into K-12 education in Palestine, but these have been held back by the challenging educational environment. However, a recent in-service training initiative, funded and organized by the Ministry or Education of Palestine, constitutes a significant effort to embed computational thinking in K-12 practice. The middle school teachers who participated in the training course were invited to participate in the present study, and 38 did so. A qualitative approach involving both interviews with teachers and classroom observations was used in data collection. All the teachers agreed to be observed in their classrooms, while 20 of the 38 also agreed to participate in the interviews. The findings showed that teachers of a range of topics, including social sciences and languages, employed computational thinking skills in teaching their students, but they were confronted by a number of challenges, including technical infrastructure and support, and a lack of time to prepare CT classes and space in the curriculum to deliver them. The results indicate that the most appropriate action to support teachers’ delivery of CT would be to provide peer exchanges and expert coaching in the integration of CT in the curriculum.