Voluminous Paleozoic sandstone sequences were deposited in northern Africa and Arabia following an extended Neoproterozoic orogenic cycle that culminated in the assembly of Gondwana. We measured sensitive high-resolution ion microprobe (SHRIMP) U-Pb ages of detrital zircons separated from several Cambrian units in the Elat area of southern Israel in order to unravel their provenance. This sandstone forms the base of the widespread siliciclastic section now exposed on the periphery of the Arabian-Nubian shield in northeastern Africa and Arabia. Most of the detrital zircons we analyzed yielded Neoproterozoic concordant ages with a marked concentration at 0.55–0.65 Ga. The most likely provenance of the Neoproterozoic detritus is the Arabian-Nubian shield; 0.55–0.65 Ga was a time of posttectonic igneous activity, rift-related volcanism, and strike-slip faulting there. Of the zircons, 30% yielded pre-Neoproterozoic ages grouped at 0.9–1.1 Ga (Kibaran), 1.65–1.85 Ga, and 2.45–2.7 Ga. The majority of the pre-Neoproterozoic zircons underwent Pb loss, possibly as a consequence of the Pan-African orogeny resetting their provenance. Rocks of the Saharan metacraton and the southern Afif terrane in Saudi Arabia (∼1000 km south of Elat) are plausible sources of these zircons. Kibaran basement rocks are currently exposed more than 3000 km south of Elat (flanking the Mozambique belt), but the shape of the detrital zircons of that age and the presence of feldspar in the host sandstone are not fully consistent with such a long-distance transport. Reworking of Neoproteorozoic glacial detritus may explain the presence of Kibaran detrital zircons in the Cambrian of Elat, but the possibility that the Arabian-Nubian shield contains Kibaran rocks (hitherto not recognized) should also be explored.