This article works at the intersection of creative, participatory and critical research. It explores an emergent qualitative methodology that is creative and participatory but not is always as critical as it might be: collaborative storytelling or storying. Understandings of critical collaborative storytelling and (more generically and inclusively) storying are developed through an account of a series of storying workshops. In these workshops, a group of young British Muslims made a short animated film titled ‘Halal Dating’. In their animated film, the participants explored an otherwise hard-to-name part of their lives: sexual relationships. Thus, in addition to its methodological interest, this article may appeal to readers with more substantive interests in religion, young people, gender and sexuality.