The oceanic storage of anthropogenic CO2 (Cant) that humans have emitted into the atmosphere has been pivotal for counteracting climate change. Yet multi-decadal trends in the ocean interior storage of Cant have not been assessed at global scale. Here, we determine storage changes of Cant by applying the eMLR(C*) regression method to ocean interior observations collected between 1989 and 2020. We find that the global ocean storage of Cant grew by 29 ± 3 Pg C dec-1 and 27 ± 3 Pg C dec-1 (±1σ) from 1994 to 2004 and 2004 to 2014, respectively. Although the two growth rates are not significantly different, they imply a reduction of the oceanic uptake fraction of the anthropogenic emissions from 36 ± 4 % to 27 ± 3 % from the first to the second decade. We attribute this reduction to a decrease of the ocean buffer capacity and changes in ocean circulation. In the Atlantic Ocean, the maximum storage rate shifted from the Northern to the Southern Hemisphere, plausibly caused by a weaker formation rate of North Atlantic Deep Waters and an intensified ventilation of mode and intermediate waters in the Southern Hemisphere. Between 1994 and 2004, the oceanic Cant accumulation exceeded the net air-sea flux by 8 ± 4 Pg C dec-1, suggesting a loss of natural carbon from the ocean during this decade. Our results reveal a substantial sensitivity of the ocean carbon sink to climate variability and change.