Widely distributed deep-water fan sandstones of early Tertiary age form the reservoir for one of the most successful and prolific plays in the North Sea and NE Atlantic margin. Stratigraphic interpretation of a large well database provides the basis for mapping sand distribution and depositional environments in these two hydrocarbon provinces. Sand thickness maps for five Paleocene–Lower Eocene plays illustrate the intimate relationship between pre-existing structural features and sand distribution and facies in the North Sea. Large-scale depositional environment mapping gives an insight into the similarities and differences between basin evolution and sand distribution in North Sea and NE Atlantic margin basins. Both provinces were affected by the same succession of pre-break-up and syn-break-up tectonic and magmatic events that led to early Eocene continental separation and the formation of the NE Atlantic. The impact of these events was muted within the North Sea, which was protected from Paleocene rifting on the NE Atlantic margin by the Scotland–Shetland hinterland and from Paleocene–early Eocene volcanism by its more distant location. However, it was the combination of tectonic and thermal uplift of this clastic source area that contributed the large volumes of sand that accumulated in both these provinces.