While glycans underlie many biological processes, such as protein folding, cell adhesion and cell-cell recognition, deep evolution of glycosylation machinery remains an understudied topic. N-linked glycosylation is a conserved process in which mannosidases are key trimming enzymes. One of them is the glycoprotein endo-α-1,2-mannosidase which participates in the initial trimming of mannose moieties from an N-linked glycan inside the cis-Golgi. It is unique as the only endo-acting mannosidase found in this organelle. Relatively little is known about its origins and evolutionary history; so far it was reported to occur only in vertebrates. In this work, a taxon-rich bioinformatic survey to unravel the evolutionary history of this enzyme, including all major eukaryotic clades and a wide representation of animals, is presented. The endomannosidase was found to be more widely distributed in animals and other eukaryotes. The protein motif changes in context of the canonical animal enzyme were tracked. Additionally, the data show the two canonical vertebrate endomannosidase genes, MANEA and MANEAL, arose at the second round of the two vertebrate genome duplications and one more vertebrate paralog, CMANEAL, is uncovered. Finally, a framework where N-glycosylation co-evolved with complex multicellularity is described. A better understanding of the evolution of core glycosylation pathways is pivotal to understanding biology of eukaryotes in general, and the Golgi apparatus in particular. This systematic analysis of the endomannosidase evolution is one step towards this goal.