With increasing interest for clean-label products, there is a need to develop protein ingredients with improved functional properties. Forming protein-polysaccharide electrostatic complexes has been found to improve protein functionalities. Most studies focus on complexation at pH < pI and low biopolymer concentrations. The purpose of this study was to develop and characterize heated whey protein-alginate complexes (H-CPX) formed by heating mixed solutions of 1–5% whey protein isolate (WPI) and alginate (0–1%) at pH 6.0 at 85°C for 30 min. Characterizations of H-CPX included measuring particle size, zeta potential and rheological properties as well as turbidity observation. Results showed that, across all WPI concentrations, average mean diameters of H-CPX significantly decreased (P < 0.05) with increasing alginate concentration until reaching a minimum and then increased. This corresponded to the change in turbidity of the H-CPX. Zeta potential results revealed that increasing alginate concentration led to the formation of H-CPX with higher negative charge, suggesting that more alginate was incorporated into the electrostatic complexes. At similar alginate concentrations, higher WPI concentration resulted in complexes with larger aggregate sizes but lower negative charge than those of H-CPX formed at lower WPI concentration. This indicated a limited degree of complexation. H-CPX formed at 1% protein showed Newtonian behavior while those formed at 5% protein became highly psuedoplastic and more viscous. It can be concluded that, with decreased particle size and increased negative charge, heated WPI-alginate complexes could potentially be utilized as natural ingredients with improved heat stability and interfacial properties.