Through the 1990s and into the new millennium, Australian children's literature responded to a conservative turn epitomised by the Howard government and to new world order imperatives of democracy, the market economy, globalisation, and the IT revolution. These responses are evidenced in the ways that children's fiction speaks to the problematics of representation and cultural identity and to possible outcomes of devastating historical and recent catastrophes. Consequently, Australian children's fiction in recent years has been marked by a dystopian turn. Through an examination of a selection of Australian children's fiction published between 1995 and 2003, this paper interrogates the ways in which hope and warning are reworked in narratives that address notions of memory and forgetting, place and belonging. We argue that these tales serve cautionary purposes, opening the way for social critique, and that they incorporate utopian traces of a transformed vision for a future Australia. The focus texts for this discussion are: Secrets of Walden Rising (Allan Baillie, 1996), Red Heart (Victor Kelleher, 2001), Deucalian (Brian Caswell, 1995), and Boys of Blood and Bone (David Metzenthen, 2003).