The Rhodopian Orogen developed since the Late Cretaceous–early Eocene during accretionary processes following the closure of the Vardar ocean basin, a branch of Neotethys. Through a multidisciplinary approach, including sandstone petrology and geochemistry of the clastic and volcanoclastic sediments, we reconstruct the unroofing history of the Rhodopian orogen and characterize the formation and the evolution of the western portions of the Thrace basin, in Greece and Bulgaria, between the late Eocene and Oligocene. Detrital modes of 127 sandstone samples provide evidence of three distinctive petrofacies: quartzolithic, quartzofeldspathic, and volcanoclastic. The petrographic composition gives evidence of contributions from three key source areas corresponding to the three main tectonic units: the Circum-Rhodope Belt, the Variegated Complex (ultramafic complex), and the Gneiss–Migmatite Complex. The three petrofacies reflect multiple provenance from different tectonic settings as they evolve from quartzolithic to quartzofeldspathic to volcanoclastic, corresponding to collisional orogen, crustal block uplift, and volcanic arc settings, respectively. Geochemical data on major elements and trace elements are used to discuss the efficacy of tectonic-setting discrimination diagrams and compare them to the Dickinson model as well as to distinguish and characterize (i) petrographically homogeneous gneiss-supplied subbasins and (ii) volcanic contributions to sandstone composition. Multivariate statistical techniques are used to unravel the complex web of factors controlling sediment composition. Biplot analysis highlights the influence of two independent processes: (1) mixing between carbonate and silicate phases, and (2) evolution from mafic to felsic source rocks. The latter indicates progressively increasing supply rates from deeper crustal levels. The compositional evolution of the sandstone suites of Thrace basin in NE Greece and SE Bulgaria is strictly related to various geodynamic stages of the Rhodope region. Provenance analysis of Thrace sandstones provide an example of the changing nature of orogenic belt sand associate basins through time, and may contribute to the general understanding of similar geodynamic settings.