Computational thinking (CT) education reaches only a fraction of young children, in part because CT learning tools often require expensive hardware or fluent literacy. Informed by needfinding interviews, we developed a voice-guided smartphone application leveraging storytelling as a creative activity by which to teach CT concepts to 5- to 8-year-old children. The app includes two storytelling games where users create and listen to stories as well as four CT games where users then modify those stories to learn about sequences, loops, events, and variables. We improved upon the app design through wizard-of-oz testing (N = 28) and iterative design testing (N = 22) before conducting an evaluation study (N = 22). Children were successfully able to navigate the app, effectively learn about the target computing concepts, and, after using the app, children demonstrated above-chance performance on a near transfer CT concept recognition task.