Climate-induced habitat change has often been invoked as an important driver of speciation and evolutionary radiation in cichlid fishes, yet studies linking morphological change directly to long-term environmental fluctuations are scarce. Here, we track changes through time in the oral dentition of Oreochromis hunteri, the endemic and only indigenous fish species inhabiting the East African crater Lake Chala (Kenya/ Tanzania), in relation to climate-driven lake-level fluctuations during the last 25,000 yr. Fossil teeth were recovered from six periods representing alternating high and low lake-level stands associated with late-Pleistocene and Holocene trends in rainfall and drought To construct a reference framework for morphological variation in fossil assemblages, we first analyzed the variability in oral tooth morphology within the modern-day fish population. These analyses established that, like other cichlids, O. hunteri gradually replace their bicuspid/tricuspid oral dentition with more unicuspid teeth as they grow. In the fossil assemblages, we found systematic and recurrent changes in the relative abundance of these oral tooth types, with a higher proportion of unicuspids during low-stands. Moreover, O. hunteri living during low-stands systematically developed unicuspid dentition at a smaller body size, compared with conspecifics living during high-stands. Considering that low-stand conditions created a sizable area of oxygenated soft-bottom habitat that is lacking during high-stands, we propose that the associated change in oral dentition reflects the fishes' exploitation of this new habitat either for feeding or for reproduction. The recurrent nature of the observed shifts provides evidence for the ability of O. hunteri to systematically adapt to local habitat change, and strongly suggests that morphological change in oral dentition promoted its long-term population persistence in an aquatic ecosystem presenting the dual challenge of being both sensitive to climate change (creating constantly shifting selective pressures) and isolated from surrounding populations (limiting gene flow). In Lake Chala, ancient climate-driven lake-level fluctuations did not directly promote speciation in O. hunteri, but the population bottlenecks they may have caused potentially contributed to its divergence from sister species Oreochromis jipe.