The Lower Cretaceous Nubian sandstones cover large areas in both NE Africa and Arabia. In this study, we utilized major and trace element data in combination with petrographic and heavy mineral analyses to infer the provenance model of the Nubian sandstones exposed at Gebel Duwi in the Eastern Desert of Egypt. It is established that these sandstones are mainly quartzose (quartz-arenite) and litho-quartzose deposited in fluvial and estuarine near-shore environments. The quartzose sandstones are dominantly fine to medium-grained in texture. The framework consists mainly of quartz grains (average 92.26% of rock volume), in addition to minor lithic fragments (average 4.6%), very rare feldspars (average 1.17%), and heavy mineral fractions (average 1.8%). The lithic fragments are represented mainly by siltstone and sandy siltstone, with minor lithics of gneisses. The heavy mineral assemblage comprises zircon, tourmaline, rutile (ZTR), garnet, and kyanite, with minor epidote, ilmenite, and leucoxene. Chemically, these sandstones are rich in SiO2 and poor in CaO, MgO, K2O, Na2O, and P2O5. From trace elements, the most abundant are Ba, Th, Zr, and Sr. The provenance-related interpretations of the established rock composition imply that the Nubian sandstones were sourced mainly from a relatively proximal Paleozoic sandstones through multiple stages of fluvial recycling and were deposited in low-lying basin areas in the passive continental margin. The modal composition analysis reflects that these sandstones are mainly of cratonic interior. The ZTR-dominated heavy mineral assemblage indicates an increasing proportion of detritus recycled from older siliciclastic units of Paleozoic age. The high chemical weathering indices indicate intense subaerial weathering in a humid environment and multiple episodes of reworking, with a considerable contribution of basement denudation. A stable tectonic regime is interpreted, and intracratonic activation is not recognized.