Sedimentologic, stratigraphic, compositional, and structural data from four elongate basins (<15 km wide, >30 km long) in the Nangqian-Yushu region of east-central Tibet (near the headwaters of the Mekong and Yangtze Rivers) indicate nonmarine sedimentation synchronous with Paleocene–Eocene northeast-southwest shortening. Sedimentation in the Nangqian, Niuguoda, Xialaxiu, and Shanglaxiu basins involved (1) mud and carbonate accumulation in offshore to nearshore lacustrine environments and (2) gravel and sand deposition in fan-delta to alluvial-fan environments localized near basin margins. Growth strata in both fine- and coarse-grained deposits, primarily in upper levels of basin fill, provide evidence for sedimentation contemporaneous with motion on fold-thrust structures. Provenance data collected from 25 measured stratigraphic sections, including >1500 paleocurrent measurements and >150 conglomerate compositional analyses, show that each basin was fed sediment from several directions by proximal source areas composed of Carboniferous–Triassic rocks. The source-area proximity and a stratigraphic variability among the basins suggest that each basin evolved independently and was filled by sediment derived from relatively small drainage networks (<103 km2). Age control for basin fill is based on Paleogene fossils, 38–37 Ma 40Ar/39Ar ages from volcanic rocks interbedded with uppermost strata of the Nangqian basin, and 51–49 Ma 40Ar/39Ar ages from igneous rocks that intrude and unconformably overlie strata of the Shanglaxiu basin. Strata containing middle Cretaceous palynomorph and ostracod assemblages are present only locally in the lowermost part of the Nangqian basin. Although the tectonic setting for Cretaceous sedimentation is unclear, early Tertiary basin development was controlled by thin-skinned fold-thrust deformation. We interpret the narrow widths of Paleocene–Eocene basins to be a result of thrust spacing, which in turn may have been controlled by the depth to the décollement (∼5 km deep according to our balanced cross section) from which imbricate thrusts ramped up through the Carboniferous–Triassic section. Sedimentologic and provenance evidence for internal drainage, limited unroofing, and relatively low average sediment-accumulation rates in these syncontractional, plateau-interior basins indicates generally small drainage systems, short main-stem rivers, shallow regional slopes, and limited denudation in east-central Tibet during early Tertiary time. Such geomorphic conditions, which are similar to the modern low-relief interior of the Tibetan plateau, suggest that the deeply incised Mekong and Yangtze Rivers of eastern Tibet were not established until after the termination of Paleogene basin development in the region.