Knowledge of Nubia/Somalia relative motion since the Early Neogene is of particular importance in the Earth Sciences, because it (i) impacts on inferences on African dynamic topography; and (ii) allows us to link plate kinematics within the Indian realm with those within the Atlantic basin. The contemporary Nubia/Somalia motion is well known from geodetic observations. Precise estimates of the past-3.2-Myr average motion are also available from paleo-magnetic observations. However, little is known of the Nubia/Somalia motion prior to ∼3.2 Ma, chiefly because the Southwest Indian Ridge spread slowly, posing a challenge to precisely identify magnetic lineations. This also makes the few observations available particularly prone to noise. Here we reconstruct Nubia/Somalia relative motions since ∼20 Ma from the alternative plate-circuit Nubia-Arabia-Somalia. We resort to trans-dimensional hierarchical Bayesian Inference, which has proved effective in reducing finite-rotation noise, to unravel the Arabia/Somalia and Arabia/Nubia motions. We combine the resulting kinematics to reconstruct the Nubia/Somalia relative motion since ∼20 Ma. We verify the validity of the approach by comparing our reconstruction with the available record for the past ∼3.2 Myr, obtained through Antarctica. Results indicate that prior to ∼11 Ma the total motion between Nubia and Somalia was faster than today. Furthermore, it featured a significant strike-slip component along the Nubia/Somalia boundary. It is only since ∼11 Ma that Nubia diverges away from Somalia at slower rates, comparable to the present-day one. Kinematic changes of some 20% might have occurred in the period leading to the present-day, but plate-motion steadiness is also warranted within the uncertainties.