Understanding culture and cultural difference has emerged as a keystone project for plural democratic societies worldwide. In the age of globalisation and global tensions, recognising and coming to know different ways of engaging with the world is a crucial component in learning to live with cultural difference in multicultural societies. One way that culture can come to be understood, cultivated and evolve over time is through stories. The study that this paper reports on constructs, deconstructs and reconstructs stories of encounters with cultural difference in secondary schools to examine the complex constructs and negotiations of culture, identity and difference across diverse school contexts. This paper pays attention to socio-cultural context and the politics of culture and difference, while acknowledging the ‘traces’ of collective and personal histories in the stories of cultural difference circulating in schools. In doing so, fertile ground is sown for thinking about the complications for teachers when negotiating intercultural understanding with their students. As intercultural understanding is now widely accepted as an education priority for multicultural societies worldwide, stories and storytelling provides opportunity to approach cultural difference and intercultural understanding from a necessarily human and relational standpoint, rather than reducing cultural difference to an opposed and opposing ‘other’, and intercultural understanding to a set of stagnant and reductive standards set by hegemonic institutions and structures.