Seven natural polymers namely, chitosan (CHI), dextran (Dex), carboxymethyl cellulose (CMC), sodium alginate (ALG), pectin (PEC), hydroxylethyl cellulose (HEC), and Gum Arabic (GA) were screened for anticorrosion property towards AZ31 Mg alloy in 3.5 wt.% NaCl solution. CHI, Dex, CMC, PEC, and GA accelerated the corrosion while ALG and HEC moderately inhibited the corrosion of the alloy. HEC and ALG (1 g/L) protected the alloy by 64.13 % and 58.27 %, respectively. Two inhibitor cocktails consisting of either HEC or ALG, KI, and Date palm seed oil have been formulated. HEC- and ALG-formulations inhibited the alloy corrosion by 80.56 % and 77.43 %, respectively from EIS technique. Surface observation studies using SECM, AFM, SEM, and EDX agreed with other experimental results revealing effective corrosion inhibition by the formulations. X-ray photoelectron spectroscopy, FTIR, and UV-vis results disclose that Mg(OH) co-existed with adsorbed inhibitor complexes.