Bacterial flagellar rod structure is built across the peptidoglycan (PG) layer. A Salmonella enterica flagellar protein FlgJ is believed to consist of two functional domains, the N-terminal half acting as a scaffold or cap essential for rod assembly and the C-terminal half acting as a PG hydrolase (PGase) that makes a hole in the PG layer to facilitate rod penetration. In this study, molecular data analyses were conducted on FlgJ data sets sampled from a variety of bacterial species, and three types of FlgJ homologs were identified: (i) “canonical dual-domain” type found in β- and γ-proteobacteria that has a domain for one of the PGases, acetylmuramidase (Acm), at the C terminus, (ii) “non-canonical dual-domain” type found in the genus Desulfovibrio (δ-proteobacteria) that bears a domain for another PGase, M23/M37-family peptidase (Pep), at the C terminus and (iii) “single-domain” type found in phylogenetically diverged lineages that lacks the Acm or Pep domain. FlgJ phylogeny, together with the domain architecture, suggested that the single-domain type was the original form of FlgJ and the canonical dual-domain type had evolved from the single-domain type by fusion of the Acm domain to its C terminus in the common ancestor of β- and γ-proteobacteria. The non-canonical dual-domain type may have been formed by fusion of the Pep domain to the single-domain type in the ancestor of Desulfovibrio. In some lineages of γ-proteobacteria, the Acm domain appeared to be lost secondarily from the dual-domain type FlgJ to yield again a single-domain type one. To rationalize the underlying mechanism that gave rise to the two different types of dual-domain FlgJ homologs, we propose a model assuming the lineage-specific co-option of flagellum-specific PGase from diverged housekeeping PGases in bacteria.