© The Authors 2015. Published by Oxford University Press on behalf of The Royal Astronomical Society. Reconstructions of the history of convergence between the Nubia and Eurasia plates constitute an important part of a broader framework for understanding deformation in the Mediterranean region and the closing of the Mediterranean Basin. Herein, we combine high-resolution reconstructions of Eurasia-North America and Nubia-North America Plate motions to determine rotations that describe Nubia-Eurasia Plate motion at ~1 Myr intervals for the past 20 Myr. We apply trans-dimensional hierarchical Bayesian inference to the Eurasia-North America and Nubia-North America rotation sequences in order to reduce noise in the newly estimated Nubia-Eurasia rotations. The noise-reduced rotation sequences for the Eurasia-North America and Nubia-North America Plate pairs describe remarkably similar kinematic histories since 20 Ma, consisting of relatively steady seafloor spreading from 20 to 8 Ma, ~20 per cent opening-rate slow