In this paper we specify and validate three interaction design patterns for an interactive storytelling experience with an autonomous social robot. The patterns enable the child to make decisions about the story by talking with the robot, reenact parts of the story together with the robot, and recording self-made sound effects. The design patterns successfully support children's engagement and agency. A user study (N = 27, 8-10 y.o.) showed that children paid more attention to the robot, enjoyed the storytelling experience more, and could recall more about the story, when the design patterns were employed by the robot during storytelling. All three aspects are important features of engagement. Children felt more autonomous during storytelling with the design patterns and highly appreciated that the design patterns allowed them to express themselves more freely. Both aspects are important features of children's agency. Important lessons we have learned are that reducing points of confusion and giving the children more time to make themselves heard by the robot will improve the patterns efficiency to support engagement and agency. Allowing children to pick and choose from a diverse set of stories and interaction settings would make the storytelling experience more inclusive for a broader range of children. © 2020 Association for Computing Machinery.