Earliest Carboniferous stromatolites were found in the Qianheishan (QHS) Formation in the Dashuigou section, Gansu Province, northwestern China. These stromatolites are exposed in a conglomerate-dominated succession of about 22.5 m in thickness, which can be traced laterally for more than 200 m in outcrop. They consist mainly of micrite, peloids, oncoids, silt-sized quartz grains, and sparry calcite with rare fine to coarse quartz grains and bioclasts. The occurrence of marine fossils (e.g., bryozoans) and fenestral structures in the stromatolites suggests that they developed in intertidal environments. Three types of stromatolite laminae were distinguished including micritic laminae, grain-dominated mixed laminae, and micrite-dominated mixed laminae. These laminae are separated by thin micritic crusts and form two lamination styles of repetitive lamination and alternating lamination. The development of grain-rich and micrite-rich laminae in the stromatolites implies that they were formed by the combination of microbial baffling, binding, and calcification. Facies analysis suggests that growth and demise of the stromatolites were controlled by relative sea-level changes. They grew during a continuous relative sea-level rise, indicated by variations in their thickness and morphology. Stromatolites change from thin-bedded laminar forms in the lower part of the studied interval to medium-bedded wavy-laminar forms and thick-bedded domal forms in the middle and upper parts, respectively. Their demise was triggered by dramatic relative sea-level fall, evidenced from the sandstone facies overlying the stromatolite interval. The occurrence of the QHS stromatolites provides an excellent example for microbial proliferation and profound changes in the marine biosphere after the end-Devonian Hangenberg extinction event.