Analysis of in-situ-produced 10Be and 26Al in 52 fluvial sediment samples shows that millennial-scale rates of erosion vary widely (7 to 366 m Ma-1) through the lithologically and topographically complex Rio Puerco Basin of northern New Mexico. Using isotopic analysis of both headwater and downstream samples, we determined that the semi-arid, Rio Puerco Basin is eroding, on average, about 100 m Ma-1. This rapid rate of erosion is consistent with estimates made using other techniques and is likely to result from a combination of easily eroded lithologies, sparse vegetation, and monsoon-dominated rainfall. Data from 331 stream water samples collected by the US Geological Survey between 1960 and 1995 are consistent with basin-wide, average chemical denudation rates of only about 1??4 m Ma-1; thus, the erosion rates we calculate may be considered rates of sediment generation because physical weathering accounts for almost 99 per cent of mass loss. The isotopic data reveal that sediment is generally well mixed downstream with the area-weighted average sediment generation rate for 16 headwater samples (234 ton km-2 a-1 for basin area 170 to 1169 km2) matching well that estimated from a single sample collected far downstream (238 ton km-2 a-1, basin area = 14 225 km2). A series of 15 samples, collected from an arroyo wall and representing deposition through the late Holocene, indicates that 10Be concentration in sediment delivered by the fluvial system has not changed appreciably over the last 1200 years despite at least two cycles of arroyo cutting and filling. Other samples (n = 21) were collected along the drainage network. Rio Puerco erosion rates scale directly with a variety of metrics describing vegetation, precipitation, and rock erodibility. Using the headwater basins for calibration, the erosion rates for both the downstream samples and also the data set as a whole, are best modelled by considering a combination of relief and vegetation metrics, both of which co-vary with precipitation and erodibility as inferred from lithology. On average, contemporary sediment yields, determined by monitoring suspended-sediment discharge, exceed cosmogenically determined millennial-scale erosion rates by nearly a factor of two. This discrepancy, between short-term rates of sediment yield and long-term rates of erosion, suggests that more sediment is currently being exported from the basin than is being produced. Because the failure of incised channel walls and the head cutting of arroyo complexes appear to be the main sources of channel sediment today, this incongruence between rates of sediment supply and sediment yield is likely to be transitory, reflecting the current states of the arroyo cycle and perhaps the influence of current or past land-use patterns. Copyright ?? 2005 John Wiley & Sons, Ltd.