Sodium caseinate or whey protein isolate-carboxymethylcellulose microcapsules were prepared by the complex coacervation method and loaded with β-pinene as a model volatile compound. The effect of varying the concentration of two food-grade reticulating agents, namely glycerol and tannic acid, on the effectiveness of volatile constituent's encapsulation was investigated. The produced microcapsules were characterised in terms of encapsulation process parameters (yield, loading, efficiency) and morphology, and the results were explained in accordance with Fourier-transform infrared spectroscopy and thermogravimetric analysis. The β-pinene's content was measured by gas chromatography. Glycerol addition led to a more than twofold increase in encapsulation efficiency, while the incorporation of tannic acid did not succeed to enhance it. Additionally, a more plastic than powdery texture and a more consistent structure with low porosity was obtained when glycerol was used. Both reticulating agents were found to act through hydrogen bonding as well as hydrophobic interactions. Molecular size difference between glycerol and tannic acid were considered responsible for the observed dissimilarities.