We detail the design of the Department of Hidden Stories (DoHS), a mobile-based game to support playful digital storytelling among primary school children in public libraries. Through a process of iterative design in collaboration with library staff and children's writers we designed DoHS to support the potential for playful storytelling through interactions with books. A deployment of DoHS with two classes of 8 to 10 years olds as part of their regular library visits revealed insights related to how to balance the expectations of a child-at-play and the requirement to further develop their creative reading and writing skills. Based on our experiences we recommend that designers create playful digitally based activities that encourage children to explore libraries and experience new interactions with physical books.