Reef-building in metazoans represents an important ecological innovation whereby individuals collectively enhance feeding efficiency and gain protection from competitors and predation. The appearance of metazoan reefs in the fossil record therefore indicates an adaptive response to complex ecological pressures. In the Nama Group, Namibia, we found evidence of reef-building by the earliest known skeletal metazoan, the globally distributed Cloudina, similar to 548 million years ago. These Cloudina reefs formed open frameworks without a microbial component but with mutual attachment and cementation between individuals. Orientated growth implies a passive suspension-feeding habit into nutrient-rich currents. The characteristics of Cloudina support the view that metazoan reef-building was promoted by the rise of substrate competitors and predators.