We studied the relative roles of environmental species sorting and priority effects in the assembly of ecological communities on long time scales, by analyzing community turnover of water fleas (Daphnia) in response to strong and recurrent environmental change in a fluctuating tropical lake. During the past 1800 years, Lake Naivasha (Kenya) repeatedly fluctuated between a small saline pond habitat during lowstands and a large freshwater lake habitat during highstands. Starting from a paleoecological reconstruction, we estimated the role of priority effects in Daphnia community assembly across 16 of these habitat turnovers and compared this with the response of the community to reconstructed changes in three environmental variables important for species sorting. Our results indicate that the best predictor of Daphnia community composition during highstands was the community composition just prior to the transition from lowstands to highstands. This reflects a long-lasting priority effect of late lowstand communities on highstand communities, arising when remnant lowstand populations fill newly available ecological space in the rapidly expanding lake habitat. Species sorting and priority effects had a comparable but relatively small influence on community composition during the lowstands. Moreover, these priority effects decayed rapidly with time as Daphnia communities responded to environmental change, in contrast with the highstand communities where priority effects lasted for several decades.