Aqueous dispersions of sodium caseinate-maltodextrin (NaCas-MD) conjugates were prepared by heating to study the impact of Maillard reaction on protein functionality. Conjugation with MD affected rheological properties, colour and microstructure of NaCas-MD dispersions. Gelation temperature of NaCas-MD dispersions increased by 7 °C after conjugation, whereas the gelation time was not significantly affected. Shear thickening of the dispersions occurred at high shear rates, and temperature-viscosity relationship was described by the Arrhenius equation. Gels formed at 25 °C had a lower gel strength after conjugation, associated with changes in microstructure. Strain hardening appeared at large amplitude oscillatory shear, which was more profound after conjugation. Moreover, a higher dextrose-equivalent-value of maltodextrin resulted in conjugates with higher degree of conjugation, darker colour, and larger particulates on a microscale. The study indicates that rheological properties of NaCas can be modified by conjugation with maltodextrin, which is in principle applicable for other protein-polysaccharide combinations.