Nonlinear storage-discharge relations may explain important hydrologic features frequently observed under a variety of environmental conditions. In this paper the catchment dynamic storage problem is addressed by incorporating nonlinear storage-discharge relations in a stochastic framework to derive the statistical distribution and the duration curve of streamflows in river basins. Such a goal is achieved by extending recent analytical solutions for the seasonal probability distribution of discharges derived from the stochastic description of soil moisture dynamics at basin scales. Long-term probability density functions (pdf's) and flow duration curves are expressed through climatic, ecohydrologic, and geomorphic parameters of the basin by relaxing the linear reservoir assumption of subsurface flow components conveniently made in previous studies. In particular, this paper focuses on three different types of nonlinear, algebraic relationships between instantaneous discharges and storage volumes (concave and convex power laws and hyperbolic). Exact expressions of the streamflow pdf are derived in all cases, which are also tested by numerical simulations. Streamflow statistics and duration curves, estimates of catchment dynamic storages, recession timescales, and sensitivity to the underlying rainfall regime are then discussed. The model shows that different shapes of the streamflow pdf (bell shaped, monotonously decreasing, and bimodal) arise depending on the degree of nonlinearity of the storage-discharge relation, providing a new approach to catchment hydrology characterization.