A new cryptostome bryozoan, Prophyllodictya simplex sp. nov., is described from the Nantzinkuan Formation (Lower Ordovician, lower Tremadoc) of Liujiachang, central China. This antedates the previously oldest known bryozoan by several million years. Colony morphology and the phylogenetic position of Prophyllodictya within Cryptostomata are explored. Phylogenetic analysis suggests that Cryptostomata (except Prophyllodictya) can be divided into two major groups, and that Prophyllodictya occupies a basal position in the cryptostome tree, which accords with its simple morphology and antiquity. A close relationship is evident between bryozoans from the South China palaeoplate and those from Baltica.