In the present work, the structuring and stabilising potential of flaxseed gum (FG) in whey protein isolate (WPI) cryo-hydrogels was investigated. The FG presence (0.1–1% wt.) in the heat-treated WPI dispersions (10% wt.) induced strong segregative phase separation phenomena, which were associated with a depletion flocculation mechanism. The cryotropic processing of the WPI-FG solutions led to the formation of diverse macroporous protein gel networks depending on the colloidal state of their biopolymeric precursors. Cryogel formation was primarily mediated via covalent (thiol-disulphide bond) bridging, whilst to a lesser extent, non-covalent interactions contributed to the overall stabilisation of the protein gel network. Although FG had a rather minor contribution to the formation of elastically active crosslinks (FG was partitioning mainly into the serum phase located in the macropores), its presence (at concentrations ≥0.75% wt.) improved the homogeneity and interconnectivity of the stranded protein network, whilst it reduced its colloidal instability and macroporosity.