We use geodetic and geologic observations to constrain the tectonic evolution of the Africa (AF)-Arabia (AR)-Eurasia (EU) plate system. Two phases of slowing of AF-EU convergence, each of which resulted in an ~ 50% decrease in the rate of convergence, coincided with the initiation of AF-AR continental rifting along the Red Sea and Gulf of Aden at 24 ± 4 Ma, and the initiation of oceanic rifting along the full extent of the Gulf of Aden at 11 ± 2 Ma. In addition, both the northern and southern Red Sea (AF-AR plate boundary) underwent changes in the configuration of extension at 11 ± 2 Ma, including the transfer of extension from the Suez Rift to the Gulf of Aqaba/Dead Sea fault system in the north, and from the central Red Sea basin (Bab al Mandab) to the Afar volcanic zone in the south. While AF-EU convergence slowed, the rate of AR - EU convergence remained constant within the resolution of our observations, and is indistinguishable from the present-day GPS rate. The timing of the initial slowing of AF-EU convergence (24 ± 4 Ma) corresponds to the initiation of extensional tectonics in the Mediterranean Basin, and the second phase of slowing to changes in the character of Mediterranean extension reported at ~ 11 Ma. These observations are consistent with the hypothesis that changes in AF-EU convergence, and associated AF-AR divergence, are the fundamental cause of both Mediterranean and Middle East post-Late Oligocene tectonics. We speculate about the implications of these kinematic relationships for the dynamics of AF-AR-EU plate interactions, and favor the interpretation that slowing of AF-EU convergence, and the resulting tectonic changes in the Mediterranean Basin and Middle East, resulted from a decrease in slab pull from the AR subducted lithosphere across the AR-AF, evolving plate boundary.