We use a novel proxy (growth rates of long-lived deep water fish, orange roughy) to reconstruct inferred water temperatures of intermediate water masses in both Northern and Southern Hemispheres since the mid-1800s. The data are consistent with instrumental records showing long-term warming in the Northern Hemisphere but also indicate decadal variability of intermediate depth temperatures that is coherent across the two hemispheres. This variability correlates with the dominant subpolar annular mode in each hemisphere and implies a bihemispheric oceanic response to external forcing that influences the properties of intermediate depth water masses.