Published research emphasizes rapid downstream export of terrestrial carbon from mountainous headwater rivers, but little work focuses on mechanisms that create carbon storage along these rivers, or on the volume of carbon storage. Here we estimate organic carbon stored in diverse valley types of headwater rivers in Rocky Mountain National Park, CO, USA. We show that low-gradient, broad valley bottoms with old-growth forest or active beaver colonies store the great majority of above- and below-ground carbon. These laterally unconfined valley segments constitute <25% of total river length, but store ∼ 75% of the carbon. Floodplain sediment and coarse wood dominate carbon storage. Our estimates of riverine carbon storage represent a previously undocumented but important carbon sink. Our results indicate that: not all mountainous rivers rapidly export carbon; not all valley segments are equally important in carbon storage; and historical changes in riverine complexity have likely reduced carbon storage.