Phylogenetic relationships and the timing of evolutionary events are essential for understanding evolution on longer time scales. Cheilostome bryozoans are a group of ubiquitous, species-rich, marine colonial organisms with an excellent fossil record but lack phylogenetic relationships inferred from molecular data. We present genome-skimmed data for 395 cheilostomes and combine these with 315 published sequences to infer relationships and the timing of key events among c. 500 cheilostome species. We find that named cheilostome genera and species are phylogenetically coherent, rendering fossil or contemporary specimens readily delimited using only skeletal morphology. Our phylogeny shows that parental care in the form of brooding evolved several times independently but was never lost in cheilostomes. Our fossil calibration, robust to varied assumptions, indicates that the cheilostome lineage and parental care therein could have Paleozoic origins, much older than the first known fossil record of cheilostomes in the Late Jurassic.