Fluvial erosion of bedrock occurs during occasional flood events when boundary shear stress exceeds a critical threshold to initiate incision. Therefore efforts to model the evolution of topography over long timescales should include an erosion threshold and should be driven by a stochastic distribution of erosive events. However, most bedrock incision models ignore the threshold as a second-order detail. In addition, climate is poorly represented in most landscape evolution models, so the quantitative relationship between erosion rate and measurable climatic variables has been elusive. Here we show that the presence of an erosion threshold, when combined with a well-constrained, probabilistic model of storm and flood occurrence, has first-order implications for the dynamics of river incision in tectonically active areas. First, we make a direct calculation of the critical shear stress required to pluck bedrock blocks for a field site in New York. Second, we apply a recently proposed stochastic, threshold, bedrock incision model to a series of streams in California, with known tectonic and climatic forcing. Previous work in the area has identified a weak relationship between channel gradient or relief and rock uplift rate that is not easily explained by simpler detachment-limited models. The results with the stochastic threshold model show that even low erosion thresholds, which are exceeded in steep channels during high-frequency flood events, fundamentally affect the predicted relationship between gradient and uplift rate in steady state rivers, in a manner consistent with the observed topography. This correspondence between theory and data is, however, nonunique; models in which a thin alluvial cover may act to inhibit channel incision in the low uplift rate zone also provide plausible explanations for the observed topography. Third, we explore the broader implications of the stochastic threshold model to the development of fluvial topography in active tectonic settings. We suggest that continued field applications of geomorphic models, including physically meaningful thresholds and stochastic climate distributions, are required to advance our knowledge of interactions among surficial, climatic, and crustal processes.