The Paleo-Asian Ocean (PAO) has been regarded as a long-lived ocean from Neoproterozoic to early Mesozoic, and its subduction and closure built the Central Asian Orogenic Belt (CAOB), the largest accretionary orogenic belt in Earth's history. Although the tectonic evolution of the PAO has been discussed from diverse perspectives, the spatiotemporal dynamics in the evolution of the main branch of the PAO and its relationship with the Tethys remain contentious partly because of the absence of sedimentary evidence. Specifically, as far as the Beishan Orogenic Collage (BOC) in the southernmost part of CAOB is concerned, there remain at least two key questions: how did the BOC evolve tectonically and paleogeographically through the late Paleozoic; and which ophiolitic belt represented the main branch of the PAO in the BOC? This study recognized 27 volcano-sedimentary microfacies and 14 facies associations (FAs) in nine measured Carboniferous–Permian sections from the southern BOC. FA changes in the Visean–Capitanian megasequence indicate a Visean–Moscovian regressive sequence from fore-reef slopes to tidal flats and an Artinskian–Wordian transgressive sequence from fan-deltas to abyssal plains, separated by a continental and volcanic sequence straddling the Gzhelian–Sakmarian interval. Characteristics and lateral correlation of FAs suggest an epicontinental sea during Visean–Moscovian times, followed by a marine rift basin which eventually developed into a proto-oceanic basin during the Artinskian–Wordian. Paleobiogeographic evidence further suggests that this epicontinental sea was closely linked with the Tethyan oceans. Statistical comparisons of detrital zircon ages based on data compiled from previous and the present studies supports that this sea was mainly fed from Neoproterozoic and Ordovician–Silurian rocks (ca. 983 and 425 Ma) with a sparse influx of Mesoproterozoic and Paleoproterozoic detritus (ca. 2492, 1449, and 1302 Ma). During the Artinskian–Wordian, the rift basin was connected with the PAO based on the mixed cool- and warm-temperate marine faunas of the Boreal and Tethyan realms. This rift basin is thought to have been fed by two source-to-sink provenance systems, from either Ordovician–Silurian or Early Permian rocks (ca. 450 or 277 Ma), although provenance signatures were mixed because of turbidity and other currents in deep marine environments. We thus propose a succession of Carboniferous–Permian paleogeographic reconstruction maps for the BOC based on FA correlation and paleobiogeographic features. In these reconstruction models, the PAO is inferred to have been composed of a main branch (an oceanic basin) in the northern BOC as a part of the North Tianshan–Hongshishan–Solonker–Hegenshan Ocean and an epicontinental sea that subsequently evolved into a marine rift basin in the southern BOC.