In the past decade, the geophysical data base in the northern North Atlantic and central Arctic Ocean constantly grew. Though far from being complete, the information from new aeromagnetic and seismic data north of the Jan Mayen Fracture Zone and in the Arctic Ocean, in combination with existing compiled geological and geophysical data, is used to produce paleo-bathymetric maps for several Cenozoic time intervals. This paleo-bathymetric model provides evidence for an initial deep-water exchange through the Fram Strait starting around 17 Ma. Furthermore, the model suggests that crustal rifting prior to initial seafloor spreading might have facilitated an earlier deep-water connection. The paleobathymetric model indicates that the first possibility for a deep-water overflow from the Norwegian-Greenland Sea to the North Atlantic could have been between 15 Ma and 20 Ma. This confirms that the paleo-topography of the Yermak Plateau played an important role in allowing the exchange of shallow water between the northern North Atlantic and the Arctic Ocean before the opening of the deep-water Fram Strait gateway.