Computational thinking (CT) education reaches only a fraction of young children, in part because CT learning tools often require expensive hardware or fluent literacy. Block-based programming environments address these challenges through symbolic graphical interfaces, but users often need instructor support to advance. Alternatively, voice-based tools provide direct instruction on CT concepts but can present memory and navigation challenges to users. In this work, we present Visual StoryCoder, a multimodal tablet application that combines the strengths of each of these approaches to overcome their respective weaknesses. Visual StoryCoder introduces children ages 5–8 to CT through creative storytelling, offers direct instruction via a pedagogical voice agent, and eases use through a block-like graphical interface. In a between-subjects evaluation comparing Visual StoryCoder to a leading block-based programming app for this age group (N = 24), we show that Visual StoryCoder is more understandable to independent learners, leads to higher-quality code after app familiarization, and encourages personally meaningful projects.