The chapter argues for a storytelling framework for sustainable problem-based learning (PBL). An important aspect of PBL is to learn how to be responsible and answerable. Such competences can only be learnt if students interact with the world. This ethical purpose is, however, often forgotten in PBL rhetoric. We propose to address this. The 17 UN development goals are seen as a political materialization of the highest principle of all being, which is identified as the eternal recurrence and hence natality. This ethical principle is radical and implies multi-species storytelling, that is, a politics of the earth instead of the human all-to-human dominance that has caused the Sixth Extinction event that we are currently living through. The challenge of PBL in regard to sustainability is to work out new institutional, economic and material practices in which the UN goals can be enacted. We propose a terra-political framework, which implies regrouping and prioritizing the UN development goals. Terra-politics is a multi-species storytelling, which can be organized as concrete problems of the earth, which are always inherent and entangled with the problems that students identify through self-directed collaborative learning processes. A terra-politics is in this sense at the heart of almost any problem that students are dealing with. We suggest that a model of true storytelling can be extended to a multi-species storytelling that we describe in four phases and seven principles. True storytelling becomes a model that can bridge strategies, communities, spaces, geographies, nature and people. Stories are seen as collective, relational and material and require the community of a Terrapolis in which being-togetherness in time-space is a guiding principle for shaping a sustainable future.