The Himalayan mountains are dissected by some of the deepest and most impressive gorges on Earth. Constraining the interplay between river incision and rock uplift is important for understanding tectonic deformation in this region. We report here the discovery of a deeply incised canyon of the Yarlung Tsangpo River, at the eastern end of the Himalaya, which is now buried under more than 500 meters of sediments. By reconstructing the former valley bottom and dating sediments at the base of the valley fill, we show that steepening of the Tsangpo Gorge started at about 2 million to 2.5 million years ago as a consequence of an increase in rock uplift rates. The high erosion rates within the gorge are therefore a direct consequence of rapid rock uplift.