This paper gives an example of how computer-based problem-solving scenarios can be embedded in a course on sustainability, in order to illustrate the highly versatile way in which such scenarios can be used to structure and evaluate learning on complexity on an individual level, as well as learning in diverse groups. After defining criteria, a computer-based problem-solving scenario has to meet in order to be useful for training competencies associated with confronting complexity, the application of one specific scenario, the Genetics Lab, is empirically evaluated on base of three student cohorts. Results suggest that existing approaches to sustainability education can be substantially complemented by computer-based problem-solving scenarios, offering genuine learning opportunities and deepening and personalizing the comprehension of known phenomena in complex problem-solving. The paper closes by offering lessons learned from the presented approach and gives advice and outlook on future applications of such scenarios in sustainability education.