The non-linear reliance of channel steepness on erosion rates can be reconciled by the stochastic-threshold incision model that incorporates river incision threshold and discharge probability distribution into erosion efficiency. Here, we explored the usage of the model in river longitudinal profile inversion, by assuming time-dependent tectonic forcing and a linear exponent that relates channel incision to slope. We developed an analytical solution to the model equation and an inverse scheme to retrieve relative uplift rate history, whose validity was based on the theoretical demonstration on knickpoint preservation. Application of the inverse scheme to the main trunks of the Dadu River basin in the eastern Tibetan Plateau produced a history with two-phase increases in the uplift/incision rates, which is similar to the results from low-temperature thermochronology. Thus, our analytical procedures provide new insights into the link of tectonic uplift and river profile evolution, when channel steepness depends on erosion rates non-linearly.