New detrital zircon U-Pb age distributions from 49 late Cenozoic sandstones and Holocene sands (49 samples, n = 3922) record the arrival of extra-regional early Pliocene Colorado River sediment at Grand Wash (western USA) and downstream locations ca. 5.3 Ma and the subsequent evolution of the river’s provenance signature. We define reference age distributions for the early Pliocene Colorado River (n = 559) and Holocene Colorado River (n = 601). The early Pliocene river is distinguished from the Holocene river by (1) a higher proportion of Yavapai-Mazatzal zircon derived from Rocky Mountain basement uplifts relative to Grenville zircon from Mesozoic supra crustal rocks, and (2) distinctive (∼6%) late Eocene–Oligocene (40–23 Ma) zircon reworked from Cenozoic basins and volcanic fields in the southern Rocky Mountains and/or the eastern Green River catchment. Geologic relationships and interpretation of 135 published detrital zircon age distributions throughout the Colorado River catchment provide the interpretative basis for modeling evolution of the provenance signature. Mixture modeling based upon a modified formulation of the Kolmogorov-Smirnov statistic indicate a subtle yet robust change in Colorado River provenance signature over the past 5 m.y. During this interval the contribution from Cenozoic strata decreased from ∼75% to 50% while pre-Cretaceous strata increased from ∼25% to 50%. We interpret this change to reflect progressive erosional incision into plateau cover strata. Our finding is consistent with geologic and thermochronologic studies that indicate that maximum post–10 Ma erosion of the Colorado River catchment was concentrated across the eastern Utah–western Colorado region.