Computer Science education has a long tradition at Eötvös Loránd University, Budapest. A lot of students apply for BSc studies that consists of 6 semesters, and it provides a general overview of the world of Informatics: the appropriate mathematical and theoretical background and practice in programming and software engineering. Our experiences show three basic problems of an computer science education at BSc level in English: an inadequate level of English language skills, the lack of the basics in mathematics, and inexperience in algorithmic thinking and problem solving. When applying to the university, students are tested for English language and mathematics skills, and based on the results they might be assigned to study in a preliminary year, where they have courses that improve their skills in English and mathematics. However, there was no course that aimed at improving algorithmic thinking and problem solving skills, and students’ lack of these skills often resulted in problems and learning difficulties in the introductory programming course. This experience has inspired us to develop and start a new course (Introduction to Computational Thinking) that focuses on improving computational thinking skills, with emphasis on algorithmic thinking and problem solving skill development. The aim of our paper is to describe the structure of the course, to introduce what was done in the first semester, and present our first experiences with this course. We would like to follow our students as they progress to their first year in their university studies, look at their results in programming classes, and improve our course based on the results.