The stability of aqueous purified tara gum (TG) mixtures with sodium caseinate (NaCas) and whey protein concentrate (WPC) was investigated. Phase diagram of TG–milk proteins mixtures was obtained by measuring the sedimented fraction or the rheological parameters. The rheological behaviour was also evaluated as function of NaCas and WPC concentration, considering the zero-shear rate viscosity and the relaxation time as response variables. The rheological parameters were determined by rotational rheometry. The studied solutions presented a meta-stable condition provided by the increase in viscosity, while mixtures with NaCas at low TG concentrations sedimentation by volume exclusion occurred. The rheological behaviour of NaCas and WPC aqueous solutions approached the Newtonian and shear-thickening model, respectively. The mixtures with TG showed a pseudoplastic behaviour, approaching the Cross model. The results indicated interaction between TG and the studied proteins, expressed by an increase of zero-shear viscosity and the relaxation time at higher gum concentration.