Paleocene deep-water deposits of the Norwegian sector of the North Sea Basin are prospective for oil and gas, although little is known about their sedimentology and distribution, or the controls on their stratigraphic evolution. To help unlock the potential of this poorly explored interval, we integrate 3D seismic reflection, well logs and core data from the eastern North Viking Graben, offshore Norway. We show that thick (up to 80 m), high net to gross (N:G) (up to 90%), sandstone-rich channel-fills and sheet-like, likely lobe deposits occur on the slope–proximal basin floor, forming part of an aerially extensive fan system. Sediment dispersal and the resultant stratigraphic architecture are controlled by slope morphology. Bypass occurred on the northern, passive margin-type slope; whereas, in the south, sediment gravity currents were deflected around, and deep-water sandstones onlap and pinch-out onto an exposed rift-related fault block that generated intra-basin bathymetric relief. Pinchout of deep-water sandstone into mudstone suggests that future exploration should focus on identifying subtle stratigraphic traps on fault block flanks or at the fan fringe. This trapping style contrasts with that encountered in the UK sector of the Northern North Sea, where most Paleocene fields and discoveries are in structural traps related to the flow of Zechstein Supergroup salt.