We develop a stochastic model for the transport of stored sediment down a river channel. The model is based on probabilities of transition of particles among four different sediment storage reservoirs, called active (often mobilized), semiactive, inactive, and stable (hardly ever mobilized). The probabilities are derived from computed sediment residence times. Two aspects of sediment storage are investigated: flushing times of sediment out of a storage reservoir and changes in the quantity of sediment stored in different reservoirs due to seasonal sediment transport into, and out of, a reach. We apply the model to Redwood Creek, a gravel bed river in northern California. Although the Redwood Creek data set is incomplete, the application serves as an example of the sorts of analyses that can be done with the method. The application also provides insights into the sediment storage process. Sediment flushing times are highly dependent on the degree of interaction of the stable reservoir with the more mobile sediment reservoirs. The most infrequent and highest intensity storm events, which mobilize the stable reservoir, are responsible for the long-term shifts in sediment storage. Turnover times of channel sediment in all but the stable reservoir are on the order of 750 years, suggesting this is all the time needed for thorough interchange between these sediment compartments and cycling of most sediment particles from the initial reservoir to the ocean. Finally, the Markov model has adequately characterized sediment storage changes in Redwood Creek for 1947–1982, especially for the active reservoir. The model replicates field observation of the passage of a slug of sediment through the active reservoir of the middle reach of Redwood Creek in the 18 years following a major storm in 1964 that introduced large quantities of landslide debris to the channel.