Bacteria from the Planctomycetes, Verrucomicrobia, and Chlamydiae (PVC) superphylum are exceptions to the otherwise dominant mode of division by binary fission, which is based on the interaction between the FtsZ protein and the peptidoglycan (PG) biosynthesis machinery. Some PVC bacteria are deprived of the FtsZ protein and were also thought to lack PG. How these bacteria divide is still one of the major mysteries of microbiology. The presence of PG has recently been revealed in Planctomycetes and Chlamydiae, and proteins related to PG synthesis have been shown to be implicated in the division process in Chlamydiae, providing important insights into PVC mechanisms of division. Here, we review the historical lack of observation of PG in PVC bacteria, its recent detection in two phyla and its involvement in chlamydial cell division. Based on the detection of PG-related proteins in PVC proteomes, we consider the possible evolution of the diverse division mechanisms in these bacteria. We conclude by summarizing what is known and what remains to be understood about the evolutionary cell biology of PVC division modes.