Comparison of plate convergence with the timing and magnitude of upper crustal shortening in collisional orogens indicates both shortening deficits (200–1700 km) and significant (10–40%) plate deceleration during collision, the cause(s) for which remains debated. The Greater Caucasus Mountains, which result from postcollisional Cenozoic closure of a relict Mesozoic back-arc basin on the northern margin of the Arabia-Eurasia collision zone, help reconcile these debates. Here we use U-Pb detrital zircon provenance data and the regional geology of the Caucasus to investigate the width of the now-consumed Mesozoic back-arc basin and its closure history. The provenance data record distinct southern and northern provenance domains that persisted until at least the Miocene. Maximum basin width was likely ~350–400 km. We propose that closure of the back-arc basin initiated at ~35 Ma, coincident with initial (soft) Arabia-Eurasia collision along the Bitlis-Zagros suture, eventually leading to ~5 Ma (hard) collision between the Lesser Caucasus arc and the Scythian platform to form the Greater Caucasus Mountains. Final basin closure triggered deceleration of plate convergence and tectonic reorganization throughout the collision. Postcollisional subduction of such small (10²–10³ km wide) relict ocean basins can account for both shortening deficits and delays in plate deceleration by accommodating convergence via subduction/underthrusting, although such shortening is easily missed if it occurs along structures hidden within flysch/slate belts. Relict basin closure is likely typical in continental collisions in which the colliding margins are either irregularly shaped or rimmed by extensive back-arc basins and fringing arcs, such as those in the modern South Pacific.