Video games offer an exciting opportunity for learners to engage in computational thinking in informal contexts. This paper describes a genre of learning environments called constructionist video games that are especially well suited for developing learners' computational thinking skills. These games blend features of conventional video games with learning and design theory from the constructionist tradition, making the construction of in-game artifacts the core activity of gameplay. Along with defining the constructionist video game, the authors present three design principles central to thier conception of the genre: the construction of personally meaningful computational artifacts, the centrality of powerful ideas, and the opportunity for learner-directed exploration. Using studies conducted with two constructionist video games, the authors show how players used in-game construction tools to design complex artifacts as part of game play, and highlight the computational thinking strategies they engaged in to overcome game challenges.