Terrestrial and lacustrine Neogene and Quaternary sediments in the Libyan Fezzan provide key evidence for paleoclimate changes in the central Sahara, associated with Lake Megafezzan. Understanding of Holocene and late Pleistocene deposits is resolved, but the age of older sediments is not. We provide the first high-resolution chronology and stratigraphy of the Neogene deposits in the Fezzan Basin, and so also the central Sahara. The sediments are divided into three unconformity-bounded units, the oldest unit, comprising the Shabirinah and Brak formations, is dated using magnetostratigraphy. The Shabirinah Formation is a succession of lacustrine and fluvial units, locally with humid and arid paleosols, which progressively show evidence of increasing aridity up through the succession. The overlying Brak Formation is a pedogenically modified palustrine limestone at basin margin locations. All these units are dated to the early Aquitanian to late Serravallian in the early to mid-Miocene, having formed prior to major volcanic fields to the east. During the mid-late Aquitanian widespread stromatolitic lake sediments developed in SE Fezzan. In the late Burdigalian palustrine carbonate units developed that typically pass laterally into mixed clastic-paleosol-carbonate units that characterise basin margin situations. The Serravallian-aged Brak Formation is a highstand deposit developed during maximum lake extent, which formed due to restriction of basin drainage to the north and east, due to growth of the Jabal as Sawda volcanic centre and uplift of the SW shoulder of the Sirte Basin. Gradual aridification of the central Sahara occurred from the early Miocene, but this trend was periodically interrupted by humid phases during which Lake Megafezzan developed. The hyperaridity of the central Sahara must have developed after 11 Ma and the main drainage networks from the Fezzan Basin were established before 23 Ma, in the Oligocene indicating the great antiquity of major central Saharan river basins.