The one-dimensional solute transport models have been developed for recent decades to predict behavior and fate of solutes in rivers. Transient storage model (TSM) is the most popular model because of its simple conceptualization to consider the complexity of natural rivers. However, the TSM is highly dependent on its parameters which cannot be directly measured. In addition, the TSM interprets the late-time behavior of concentration curves in the shape of an exponential function, which has been evaluated as not suitable for actual solute behavior in natural rivers. In this study, we suggested a stochastic approach to the solute transport analysis. We delineated the model development and model application to a natural river, and compared the results of the proposed model to those of the TSM. To validate the proposed model, a tracer test was carried out in the 4.85 km reach of Gam Creek, one of the first-order tributaries of Nakdong River, South Korea. As a result of comparing the power-law slope of the tail of breakthrough curves, the simulation results from the stochastic storage model yielded the average error rate of 0.24, which is more accurate than the 14.03 and 1.87 from advection-dispersion model and TSM, respectively. This study demonstrated the appropriateness of the power-law residence time distribution to the hyporheic zone of the Gam Creek.