This study investigated the impact of heterogeneity of crosslinking on a range of physical and mechanical properties of calcium alginate networks formed via external gelation with 0.25–2% sodium alginate and 2.5 and 5% CaCl2. Crosslinking in films with 1–2% alginate was highly heterogeneous, as indicated by their lower calcium content (35–7 mg Ca·g alginate−1) and apparent solubility (5–6%). Overall, films with 1–2% alginate showed higher resistance (tensile strength = 51–147 MPa) but lower elasticity (Elastic Modulus = 2136–10,079 MPa) than other samples more homogeneous in nature (0.5% alginate, Elastic Modulus = 1918 MPa). Beads with 0.5% alginate prevented the degradation of β-carotene 1.5 times more efficiently than 1% beads (5% CaCl2) at any of the storage temperatures studied. Therefore, it was postulated that calcium alginate networks crosslinked to a greater extent and in a more homogeneous manner showed better mechanical performance and barrier properties for encapsulation applications.