The North Qilian Ocean (NQO) was the northernmost branch of the Proto-Tethys separating the Central Qilian Terrane (CQT) from the North China Block (NCB) since the Neoproterozoic Rodinia breakup. An enhanced knowledge on its evolutionary history would greatly improve our understanding on the tectonics of the Proto-Tethys and the assembly of the East Asia. However, the timing of the NQO closure onset remains unsolved with assumptions ranging from the end-Ordovician to the Devonian. To address this issue, integrated studies of stratigraphy, petrology and geochronology were conducted on the Ordovician strata in the SWNCB and the eastern North Qilian Accretionary Belt (ENQAB). Stratigraphic and paleontologic syntheses demonstrate that the pre-Katian strata in the SWNCB are shallow-marine deposits containing abundant benthonic faunas, while the Katian successions atop an unconformity are dominated by deep-water calcareous debrites and siliciclastic turbidites with the dominance of planktonic graptolites. Provenance analysis reveals an evolving source from the NCB basement to the CQT orogen since the Katian. The pre-Katian quartz arenites in the SWNCB contain zircons of ca. 1600–2800 Ma significantly older than their depositional timing, in contrast, the Katian turbidites in the SWNCB and the ENQAB display similar age patterns dominated by ca. 450–900 Ma ages. These clues imply a noteworthy basin-filling shift from passive margin to underfilled peripheral foreland separated by a forebulge unconformity at the Sandbian/Katian boundary. The first arrival of CQT-originated detritus onto the SWNCB at ca. 453 Ma is the oldest stratigraphic constraint for the initial elimination of the northern Proto-Tethys.