Mucus is characterized by multiple levels of assembly at different length scales which result in a unique set of rheological (flow) and mechanical properties. These physical properties determine its biological function as a highly selective barrier for transport of water and nutrients, while blocking penetration of pathogens and foreign particles. Altered integrity of the mucus layer in the small intestine has been associated with a number of gastrointestinal tract pathologies such as Crohn's disease and cystic fibrosis. In this work, we uncover an intricate hierarchy of intestinal mucin (Muc2) assembly and show how complex rheological properties emerge from synergistic interactions between mucin glycoproteins, non-mucin proteins, and Ca2+. Using a novel method of mucus purification, we demonstrate the mechanism of assembly of Muc2 oligomers into viscoelastic microscale domains formed via hydrogen bonding and Ca2+-mediated links, which require the joint presence of Ca2+ ions and non-mucin proteins. These microscale domains aggregate to form a heterogeneous yield stress gel-like fluid, the macroscopic rheological properties of which are virtually identical to that of native intestinal mucus. Through proteomic analysis, we short-list potential protein candidates implicated in mucin assembly, thus paving the way for identifying the molecules responsible for the physiologically critical biophysical properties of mucus.