The Kunlun fault is a major, active, left-lateral strike-slip fault upon the Tibet Plateau. Analysis of the long-term behavior of the fault is important in understanding the tectonic behavior of strike-slip faults and in assessing the mode of continental deformation and nature of seismic hazards upon the Tibet Plateau. However, our knowledge of the paleoseismicity and seismic behavior of the Kunlun fault remains limited and controversial because of difficult access, lack of field data, and the low spatial density of modern monitoring instruments. This study involved field investigations, fault-trench excavations, and an analysis of remote sensing images of the eastern (Maqen-Maqu) segment of the Kunlun fault near the town of Maqu in Gansu Province, China, revealing systematic deflections of rivers and gullies and mole track structures along the fault. Trench excavations revealed horizons of fluvial sand–gravel and silt–soil deposits, containing organic soil and peat, deformed by and offset along the fault. Based on the distribution of faulted and unfaulted sediments, fault-related structures, and age data, nine paleoseismic surface-faulting events are identified over the past 9000–10,000 yr, of which the youngest event is constrained to the past 1000–1500 yr. A millennial recurrence interval of large earthquakes is estimated with an average slip of ∼3 m. An average Holocene slip rate of 3 mm/yr is estimated for this portion of the Kunlun fault. These results, together with those of previous studies, demonstrate that the along strike-slip rate is nonuniform, diminishing toward the east at an average gradient of 1 mm/100 km. This is in contrast to previous findings that the slip rate along the Kunlun fault is uniform and on the order of 11.5±2 mm/yr.