Bacteria near-universally contain a cell wall sacculus of murein (peptidoglycan), the synthesis of which has been intensively studied for over 50 years. In striking contrast, archaeal species possess a variety of other cell wall types, none of them closely resembling murein. Interestingly though, one type of archaeal cell wall termed pseudomurein found in the methanogen orders Methanobacteriales and Methanopyrales is a structural analogue of murein in that it contains a glycan backbone that is cross-linked by a L-amino acid peptide. Here, we present taxonomic distribution, gene cluster and phylogenetic analyses that confirm orthologues of 13 bacterial murein biosynthesis enzymes in pseudomurein-containing methanogens, most of which are distantly related to their bacterial counterparts. We also present the first structure of an archaeal pseudomurein peptide ligase from Methanothermus fervidus DSM1088 (Mfer336) to a resolution of 2.5 Å and show that it possesses a similar overall tertiary three domain structure to bacterial MurC and MurD type murein peptide ligases. Taken together the data strongly indicate that murein and pseudomurein biosynthetic pathways share a common evolutionary history.