Early Cenozoic plate collision of India and Eurasia was a significant geological event, which resulted in Tibetan Plateau (TP) uplift and altered regional and global atmospheric circulations. However, the timing of initial collision is debated. It also remains unclear whether the TP was deformed either progressively northward, or synchronously as a whole. As the largest basin in the hinterland of the TP, evolution of the Hoh Xil Basin (HXB) and its structural relationship with development of the Tanggula Thrust System (TTS) have important implications for unraveling the formation mechanism and deformation history of the TP. In this study, we present results from a long sedimentary sequence from the HXB that dates the Fenghuoshan Group to ∼72–51 Ma based on magnetostratigraphy and radiometric ages of a volcanic tuff layer within the group. Three depositional phases reflect different stages of tectonic movement on the TTS, which was initialized at 71.9 Ma prior to the India–Eurasia collision. An abrupt sediment accumulation rate increase from 53.9 Ma is a likely response to tectonic deformation in the plateau hinterland, and indicates that initial India–Eurasia collision occurred at no later than that time. This remote HXB tectonosedimentary response implies that compressional deformation caused by India–Eurasia collision likely propagated to the central TP shortly after the collision, which supports the synchronous deformation model for TP.