This study presents an integrated evaluation of the burial and thermal history of an exhumed (uplifted and eroded) basin, and investigates the implications for the evolution of reservoir quality of the Ordovician sandstone in the Illizi Basin, Algeria. Complementary techniques including sonic compaction analysis, apatite fission track analysis, thermal maturity analysis, fluid inclusion microthermometry, and sandstone petrography are integrated to provide calibration for burial and thermal history models and diagenetic forward modelling, in order to predict variations in sandstone reservoir quality across the study area. The Illizi Basin has been structurally modified due to multiple exhumation events, including the uplift of the Hoggar Massif, which resulted in exhumation of the flanking sedimentary basins over a distance of 1,500 km from north to south. This study presents new apatite fission track data and analyses that constrain the onset of major exhumation in the Illizi Basin to the Eocene with exhumation magnitudes estimated to be 1-1.4 km in the study area. The study area contains a multi trillion cubic foot gas-condensate accumulation within a large four way dip closure. Hydrocarbon generation occurred during two main phases in the Carboniferous and the Mesozoic, but ceased during Cenozoic exhumation. Due to the Cenozoic tilting of the Illizi Basin in response to the uplift of the Hoggar Massif to the south, the present-day structural trap is interpreted to have formed after the main hydrocarbon generation phases. Therefore, alternative charging mechanisms of this post-peak burial trap are required and explored. In addition, new fluid inclusion data provides evidence of a significant fluid flow event within the Illizi basin, triggered by Cenozoic exhumation. Brines hosted present-day in the Ordovician sandstone in the study area are shown to be genetically linked to Triassic-Liassic evaporites deposited over 400 km to the north. Overpressure dissipation during exhumation is proposed to be a potential driving mechanism for the late stage remobilization of deep brines. A major pre-drill risk in many North African Paleozoic plays relates to sandstone reservoir quality, largely due to extensive quartz diagenesis. The Ordovician reservoir in the study area is characterised through petrography and core analysis, and the impact of burial and thermal history on the reservoir quality is investigated through diagenetic forward modelling. Results indicate that facies and variations in thermal history are a major control on preserving reservoir quality. This study demonstrates the importance of integrating the burial and thermal history, depositional facies and diagenetic history during predictive reservoir quality studies, particularly in exhumed basins where the burial and exhumation history may be complex, and present-day depth or geometry is not indicative of the past. Methodologies and implications from this study could be applied to exhumed basins in general.