Geological processes such as erosion and sedimentation redistribute toxic pollutants introduced to the landscape by mining, agriculture, weapons development, and other human activities. A significant portion of these contaminants is insoluble, adsorbing to soils and sediments after being released. Geologists have long understood that much of this sediment is stored in river floodplains, which are increasingly recognized as important nonpoint sources of pollution in rivers. However, the fate of contaminated sediment has generally been analyzed using hydrodynamic models of in-channel processes, ignoring particle exchange with the floodplain. Here, we present a stochastic theory of sediment redistribution in alluvial valley floors that tracks particle-bound pollutants and explicitly considers sediment storage within floodplains. We use the theory to model the future redistribution and radioactive decay of 137Cs currently stored on sediment in floodplains at the Los Alamos National Laboratory (LANL) in New Mexico. Model results indicate that floodplain storage significantly reduces the rate of sediment delivery from upper Los Alamos Canyon, allowing 50% of the 137Cs currently residing in the valley floor to decay radioactively before leaving LANL. A sensitivity analysis shows that the rate of sediment overturn in the valley (and hence, the total amount of radioactive 137Cs predicted to leave LANL) is significantly controlled by the rate of sediment exchange with the floodplain. Our results emphasize that flood plain sedimentation and erosion processes can strongly influence the redistribution of anthropogenic pollutants in fluvial environments. We introduce a new theoretical framework for examining this interaction, which can provide a scientific basis for decision-making in a wide range of river basin management scenarios.