Stories are made to be told, yet the computational generation of stories has principally focused on stories as textual artifacts, rather than on the telling, or indeed the performance, of stories. The performative aspect of stories, in which a teller brings a tale to life, requires more than the written word. We humans use our bodies to enact a story, through the apt use of motion, space, timing and gesture. This work explores the physical enactment of computer-generated stories using multiple robots, which narrate the tale, and take on different roles of characters within it. They use pantomime to enhance the drama of narrative events, and use naturalistic gestures for more subtle communicative effects. They also use space as a mirror for abstract concerns such as affect and social relations. The paper outlines the Scéalability framework for turning story artifacts into performances, and presents empirical findings on the effectiveness of various embodied strategies. In particular, we show that audiences are sensitive to the coherent use of space in embodied story-telling, and appreciate the schematic use of spatial movements as much as more culturally specific pantomime gestures. For the presented study, we focus on one dimension of spatial movement involving two robot actors.