Seismic wide-angle data were recorded to more than 300-km offset from powerful airgun sources during the MONA LISA experiments in 1993 and 1995 to determine the seismic-velocity structure of the crust and uppermost mantle along three lines in the southeastern North Sea with a total length of 850 km. We use the first arrivals observed out to an offset of 90 km to obtain high-resolution models of the velocity structure of the sedimentary layers and the upper part of the crystalline crust. Seismic tomographic traveltime inversion reveals 2–8-km-thick Paleozoic sedimentary sequences with P-wave velocities of 4.5–5.2 km/s. These sedimentary rocks are situated below a Mesozoic-Cenozoic sequence with variable thickness: ∼2–3 km on the basement highs, ∼2–4 km in the Horn Graben and the North German Basin, and ∼6–7 km in the Central Graben. The thicknesses of the Paleozoic sedimentary sequences are ∼3–5 km in the Central Graben, more than 4 km in the Horn Graben, up to ∼4 km on the basement highs, and up to 8 km in the North German Basin. The Paleozoic strata are clearly separated from the shallower and younger sequences with velocities of ∼1.8–3.8 km/s and the deeper crystalline crust with velocities of more than 5.8–6.0 km/s in the tomographic P-wave velocity model. Resolution tests show that the existence of the Paleozoic sediments is well constrained by the data. Hence, our wide-angle seismic models document the presence of Paleozoic sediments throughout the southeastern North Sea, both in the graben structures and in deep basins on the basement highs.