This article analyzes the process of institutionalizing interdisciplinary graduate programs in Brazil, which has over more than four decades of experience implementing masters and doctoral problem-oriented programs designed to operate outside the disciplinary structure of universities. Brazil has a high degree of centrality and government regulation, requiring systematic performance reports. The main focus of this case study is the bottlenecks and lessons emerging from programs focused on sustainability, environmental management, and environment and society, all of which are strictly supervised by a national system of accreditation and evaluation. The article includes detailed presentation of one particular graduate program that has existed for twenty years, the Sustainable Development Center at the Universidade de Brasília. Several overall topics are also considered, including the idea that interdisciplinarity is an opportunity to integrate knowledge needed for confronting complex problems and does not compete with disciplinary efforts towards progress in science.