A series of sulfonated random and block copolymers were adsorbed on the surface of ~100 nm iron oxide (IO) nanoparticles (NPs) to provide colloidal stability in extremely concentrated brine composed of 8% wt NaCl + 2% wt CaCl2 (API brine; 1.4 M NaCl + 0.2 M CaCl2) at 90 °C. A combinatorial materials chemistry approach, which employed Ca(2+)-mediated adsorption of anionic acrylic acid-containing sulfonated polymers to preformed citrate-stabilized IO nanoclusters, enabled the investigation of a large number of polymer coatings. Initially a series of poly(2-methyl-2-acrylamidopropanesulfonate-co-acrylic acid) (poly(AMPS-co-AA)) (1:8 to 1:1 mol:mol), poly(styrenesulfonate-block-acrylic acid) (2.4:1 mol:mol), and poly(styrenesulfonate-alt-maleic acid) (3:1 mol:mol) copolymers were screened for solubility in API brine at 90 °C. The ratio of AMPS to AA groups was varied to balance the requirement of colloid dispersibility at high salinity (provided by AMPS) against the need for anchoring of the polymers to the iron oxide surface (via the AA). Steric stabilization of IO NPs coated with poly(AMPS-co-AA) (1:1 mol:mol) provided colloidal stability in API brine at room temperature and 90 °C for up to 1 month. The particles were characterized before and after coating at ambient and elevated temperatures by a variety of techniques including colloidal stability experiments, dynamic light scattering, zeta potential, and thermogravimetric analysis.