The effectiveness of a video tutorial versus a paper-based tutorial for software training has yet to be established. Mixed outcomes from the empirical studies to date suggest that for a video tutorial to outperform its paper-based counterpart, the former should be crafted so that it addresses the strengths of both designs. This was attempted in the present study. Two consecutive experiments were conducted to examine the effect of tutorial type (video vs. paper based) on task relevance, self-efficacy, mood, flow and task performance. Participants were students from junior high school. Both studies reported significant, positive contributions of the tutorials to task relevance, self-efficacy, mood and flow. Both studies also found significant and substantial effects on task performance. A learning gain of about 30% was achieved in both studies. A retention task, completed only in Study 2, further revealed that the learning effect was stable. More importantly, performance on this task also indicated a significant interaction with tutorial type, favouring the video. The success of the video tutorial is ascribed to its design, which attended to and even incorporated key qualities of paper-based tutorials, while also capitalizing on the strengths of video.