Over the last decade, various organisations, scholars and educators across the globe have been arguing for the need to foster dialogue between and with children regarding the world they want to have, in terms of both justice and sustainability. Research has shown that stories and storytelling have a world-making and world-changing character that may trigger children's social imagination on social justice issues and help them play a participatory role in society. In this context, the study presented here aimed to empower children to speak up for their beliefs and to become active agents of change in relation to social justice issues. To meet our research goals, we developed workshops around traditional folktales, which we implemented in four schools in Cyprus. During these workshops, we promoted critical dialogue for social justice issues through pertinent collaborative storytelling activities. Collaborative storytelling is a method that can involve participants in critical dialogue, enabling them to produce innovative and creative counter-stories. This can potentially deepen their perceptions about social justice, while also allowing them to communicate the knowledge they have built in engaging and accessible ways. Data collection included observations during workshops, as well as post-implementation interviews with a purposive sample of child participants. Our findings suggest that the children deployed either a 'we are all different' or a 'we are all the same' discourse to define social justice. Nonetheless, as the project progressed, they seemed to gradually turn to a 'we need to see injustice to be able to act against it' discourse. This project aims to contribute to academic discussions on promoting dialogue with children on social justice issues, and cultivating children's metacognitive skills about societal injustices.