Education plays a decisive role to face the global challenge of sustainability. That is the reason why the university degrees of education must aim to promote pre-service teachers’ compromise with the Agenda 2030 and provide them with the competencies, resources and methods to integrate sustainability into curricula. This paper analyses the effectiveness of a cross-curricular competency-based project involving both PBL and RBL methodologies, with storytelling as a pivotal element, which aims to achieve the two aforementioned objectives, as well as to develop prospective teachers’ multilingual competence and the transversal (higher-order, inter- and intrapersonal) skills necessary to critically reflect on the ideas of sustainable development and the values that underlie them in order to take action for sustainable development. The research uses a pre-test/post-test methodology, with no control group, a sample of 61 students which is finally complemented with a focus-group interview. The results confirm the positive effects of the project on the acquisition of criteria to select resources (mainly stories and related materials) for sustainability education, their ability to apply storytelling techniques, their oral and written academic language skills, and also the development of research skills and transversal competences, among others, creativity, critical thinking, reasoned-decision making, communication and team-work skills.