Building on coding mutations and splicing variants, post-translational modifications add a final layer to protein diversity that operates at developmental and physiological timescales. Although protein glycosylation is one of the most common post-translational modifications, its evolutionary origin remains largely unexplored. Here, we performed a phylostratigraphic tracking of glycosylation machinery (GM) genes and their targets—glycoproteins (GPs)—in a broad phylogenetic context. Our results show that the vast majority of human GM genes trace back to two evolutionary periods: the origin of all cellular organisms and the origin of all eukaryotes. This indicates that protein glycosylation is an ancient process likely common to all life, further elaborated in early eukaryotes. In contrast, human glycoproteins exhibited prominent enrichment signals in more recent evolutionary periods, suggesting an important role in the transition from metazoans to vertebrates. Focusing specifically on the N-glycosylation (NG) pathway, we noted that the majority of NG genes acting on the cytoplasmic side of the endoplasmic reticulum (ER) trace back to the origin of cellular organisms. This sharply contrasts with the rest of the NG pathway, which is oriented toward the ER lumen, where genes of eukaryotic origin predominate. In the Golgi, we also identified an analogous binary evolutionary origin of GM genes. We discuss these findings in the context of the evolutionary emergence of the eukaryotic endomembrane system and propose that the ER evolved through the invagination of a prokaryotic cell membrane containing an NG pathway.