In recent decades, the central Arctic Ocean has been experiencing dramatic decline in sea ice coverage, thickness and extent, which is expected to have a tremendous impact on all levels of Arctic marine life. Here, we analyze the regional and temporal changes in pan-Arctic distribution and population structure of the key zooplankton species Calanus glacialis and C. hyperboreus in relation to recent changes in ice conditions, based on historical (1993–1998) and recent (2007–2016) zooplankton collections and satellite-based sea ice observations. We found strong correlations between Calanus abundance/population structure and a number of sea ice parameters. These relationships were particularly strong for C. glacialis, with higher numbers being observed at locations with a lower ice concentration, a shorter distance to the ice edge, and more days of open water. Interestingly, early stages of C. hyperboreus followed the same trends, suggesting that these two species substantially overlap in their core distribution area in the Arctic Ocean. Calanus glacialis and C. hyperboreus have been historically classified as shelf versus basin species, yet we conclude that both species can inhabit a wide range of bottom depths and their distribution in the Arctic Ocean is largely shaped by sea ice dynamics. Our data suggest that the core distribution patterns of these key zooplankton are shifting northwards with retreating sea ice and changing climate conditions.