The Barents Sea sedimentary basin is one of the principle targets of oil and gas companies exploring in the Arctic region due to its potentially significant, undiscovered, hydrocarbon resources. However, whilst the Norwegian portion of the Barents Sea is covered by a dense network of seismic lines and penetrated by numerous wells, the Russian portion is comparatively poorly studied. The sedimentary succession there to date has been reconstructed from only a few wells drilled in the southern part of the basin, 4 wells drilled onshore across the Franz Joseph Land (FJL) archipelago, and onshore outcrop exposures across the FJL and Novaya Zemlya archipelagoes. However, the deeper pre-Mesozoic succession in the northeastern part of the Barents Sea has been constrained mainly by seismic data (Makariev, 2006, 2011; Basov et al., 2009; Henriksen et al., 2011) and only penetrated by the Nagurskaya well drilled on the westernmost part of FJL. Here, we present new data on the age of the pre-Mesozoic succession of FJL and the surrounding parts of the Barents Sea based on foraminiferal faunas from carbonate pebbles and cobbles collected from the Lower Jurassic conglomerates of Graham Bell Island.