U–Pb and Lu–Hf isotope analyses of detrital zircons collected from the Devonian–Permian strata of Kotel'ny Island (New Siberian Islands, Eastern Russian Arctic) provide vital information about provenance areas and history of the poorly studied Paleozoic basement of the Laptev and East Siberian shelves. Based on detrital zircon signatures, our study reveals that the studied succession can be divided into two distinct groups: Devonian–Lower Carboniferous and uppermost Carboniferous–Permian. U–Pb and Lu–Hf isotope signatures of detrital zircons from the Devonian–Lower Carboniferous deposits correspond to well-known Precambrian–Early Paleozoic magmatic and metamorphic events within the northern part of Baltica, indicative of a peri-Baltican affinity of the New Siberian Islands during this time. A lack of zircon ages close to the depositional age of the formation, along with a mature composition of the sandstones, suggest that the Devonian–Lower Carboniferous succession formed as a result of extensive sediment reworking from a distal provenance. By contrast, uppermost Carboniferous–Permian sandstones have an immature composition, with numerous young detrital zircons close to the age of sedimentation and Hf signatures typical of a continental arc environment. We therefore suggest that the provenance for these younger deposits was located within a coeval orogeny and based on previous studies, we conclude that these deposits were sourced from the north-western part of the Uralian Orogen.