Foreland basin development in the Andes of central Colombia has been suggested to have started in the Late Cretaceous through tectonic loading of the Central Cordillera. Eastward migration of the Cenozoic orogenic front has also been inferred from the foreland basin record west of the Eastern Cordillera. However, farther east, limited data provided by foreland basin strata and the adjacent Eastern Cordillera complicate any correlation among mountain building, exhumation, and foreland basin sedimentation. In this study, we present new data from the Medina Basin in the eastern foothills of the Eastern Cordillera of Colombia. We report sedimentological data and palynological ages that link an eastward-thinning early Oligocene to early Miocene syntectonic wedge containing rapid facies changes with an episode of fast tectonic subsidence starting at ca. 31 Ma. This record may represent the first evidence of topographic loading generated by slip along the principal basement-bounding thrusts in the Eastern Cordillera to the southwest of the basin. Zircon fission-track ages and paleocurrent analysis reveal the location of these thrust loads and illustrate a time lag between the sedimentary signal of topographic loading and the timing of exhumation (ca. 18 Ma). This lag may reflect the period between the onset of range uplift and significant removal of overburden. Vitrinite reflectance data document northward along-strike propagation of the deformation front and folding of the Oligocene syntectonic wedge. This deformation was coupled with a nonuniform incorporation of the basin into the wedge-top depozone. Thus, our data set constitutes unique evidence for the early growth and propagation of the deformation front in the Eastern Cordillera, which may also improve our understanding of spatiotemporal patterns of foreland evolution in other mountain belts.