Deep-water formation in the northern North Atlantic Ocean and the Arctic Ocean is a key driver of the global thermohaline circulation and hence also of global climate. Deciphering the history of the circulation regime in the Arctic Ocean has long been prevented by the lack of data from cores of Cenozoic sediments from the Arctic's deep-sea floor. Similarly, the timing of the opening of a connection between the northern North Atlantic and the Arctic Ocean, permitting deep-water exchange, has been poorly constrained. This situation changed when the first drill cores were recovered from the central Arctic Ocean. Here we use these cores to show that the transition from poorly oxygenated to fully oxygenated ('ventilated') conditions in the Arctic Ocean occurred during the later part of early Miocene times. We attribute this pronounced change in ventilation regime to the opening of the Fram Strait. A palaeo-geographic and palaeo-bathymetric reconstruction of the Arctic Ocean, together with a physical oceanographic analysis of the evolving strait and sill conditions in the Fram Strait, suggests that the Arctic Ocean went from an oxygen-poor 'lake stage', to a transitional 'estuarine sea' phase with variable ventilation, and finally to the fully ventilated 'ocean' phase 17.5 Myr ago. The timing of this palaeo-oceanographic change coincides with the onset of the middle Miocene climatic optimum, although it remains unclear if there is a causal relationship between these two events.