Sediment cores and seismic reflection data acquired from the eastern basin of Lake Kivu, Rwanda reveal extensive limnologic variations due to changes in regional climate and basin structure. The eastern basin of the lake contains a sedimentary wedge which is > 1.5 km in thickness on its western side, and basal sediments are estimated to be at least 1.5 million years old. Sediments are likely to be thicker and older than this in the northern, Congolese basin of the lake. Above the ∼300 m iosbath only a thin layer of Holocene sediments are observed indication that this may have been the lake’s high stand prior to that time. There are at least three erosional unconformities interpreted as desiccation or near-desiccation events which are estimated to have occurred at ∼475 ka, ∼100 ka, and ∼20 ka; the two most recent of these low stages likely developed during the African Megadrought and Last Glacial Maximum (LGM) periods. Following the LGM, the water levels rose to form a ∼100 m deep lake with its surface ∼370 m below the current lake level. The lake remained near that level for several thousand years and during this time the Virunga Volcanic Province expanded. At ∼12.2 ka a change to wetter climate conditions rapidly filled the lake to spill out of the Bukavu Bay basin southward toward Lake Tanganyika. Tephra sampled from the cores show that there have been at least 24 large local volcanic events since the early Holocene lake transgression.