Bryozoans (ectoprocts or moss animals) are aquatic, dominantly sessile, filter-feeding lophophorates that construct an organic or calcareous modular colonial (clonal) exoskeleton. The presence of six major orders of bryozoans with advanced polymorphisms in lower Ordovician rocks strongly suggests a Cambrian origin for the largest and most diverse lophophorate phylum. However, a lack of convincing bryozoan fossils from the Cambrian has hampered resolution of the true origins and character assembly of earliest members of the group. Here we interpret the millimetric, erect, bilaminate, secondarily phosphatised fossil Protomelission gatehousei from the early Cambrian of Australia and South China as a potential stem-group bryozoan. The monomorphic zooid capsules, modular construction, organic composition and simple linear budding growth geometry represent a mixture of organic Gymnolaemata and biomineralised Stenolaemata character traits, with phylogenetic analyses identifying P. gatehousei as a stem-group bryozoan. This aligns the origin of phylum Bryozoa with all other skeletonised phyla in Cambrian Age 3, pushing back its first occurrence by approximately 35 million years. This reconciles the fossil record with molecular clock estimations of an early Cambrian origination and subsequent Ordovician radiation of Bryozoa following the acquisition of a carbonate skeleton.