There is a pressing need to improve the sustainability of educational improvement efforts, but sustainability remains undertheorized in science education. In this article, we draw upon frameworks from organizational culture and sustainability to characterize change within a single undergraduate science department. This in-depth longitudinal case study over 15 years provides careful documentation of the types of changes that are required to make improvements over time. In particular, we argue that cultural shifts are an important aspect of sustainable improvements. As we show, even a department that was considered an educational improvement "success story" was unable to sustain the improvements made through its initial effort. Nonetheless, we do argue that the initial effort resulted in shifts to multiple aspects of the department's culture (e.g., ways of thinking, the status of education in the department), that we characterize with Bolman and Deal's four frames. These cultural shifts provided the groundwork for a later effort, to ultimately create sustainable structures in the department resulting in sustained improvement. To conclude, we provide recommendations for how to improve the sustainability of change efforts and describe important methodological considerations for future studies of sustainability.