Stromatoporoid sponges were important reef-builders during the middle Paleozoic, yet their early history and integration into reef ecosystems remain poorly understood. Here, we report Lophiostroma leizunia Jeon sp. nov., the oldest known stromatoporoid from upper Tremadocian to lower Floian (similar to 480 My-old) strata of South China. L. leizunia formed complex reef structures, playing crucial roles in framework construction and binding other components, including calcimicrobes, lithistid sponges, stalked echinoderms, and Calathium. This discovery pushes back the fossil record of stromatoporoids and the reefs that they formed by approximately 20 My, advancing the onset the Great Ordovician Biodiversification Event in reef evolution. L. leizunia unusually constructed its skeleton using fluorapatite-a feature previously unknown in sponges. This establishes Porifera as the first metazoan phylum known to have utilized all three principal biominerals: silica, calcium carbonate, and calcium phosphate. The presence of phosphatic skeletons in this early stromatoporoid expands our understanding biomineralization capabilities in early animals and suggests that the genetic toolkit for diverse biomineralization strategies may have been present in early sponges. The unique combination of the earliest known reef-building stromatoporoids and their phosphatic skeletal composition provides insights into the evolutionary dynamics biomineralization and the rise of metazoan-dominated reef ecosystems during a critical period of Earth's history.