Mg and its alloys are promising biodegradable materials for orthopedic implants and cardiovascular stents. The first interactions of protein molecules with Mg alloy surfaces have a substantial impact on their biocompatibility and biodegradation. We investigate the early-stage electrochemical, chemical, morphological, and electrical surface potential changes of alloy WE43 in either 154 mM NaCl or Hanks’ simulated physiological solutions in the absence or presence of bovine serum albumin (BSA) protein. WE43 had the lowest electrochemical current noise (ECN) fluctuations, the highest noise resistance (Zn = 1774 Ω·cm2), and the highest total impedance (|Z| = 332 Ω·cm2) when immersed for 30 min in Hanks’ solution. The highest ECN, lowest Zn (1430 Ω·cm2), and |Z| (49 Ω·cm2) were observed in the NaCl solution. In the solutions containing BSA, a unique dual-mode biodegradation was observed. Adding BSA to a NaCl solution increased |Z| from 49 to 97 Ω·cm2 and decreased the ECN signal of the alloy, i.e., the BSA inhibited corrosion. On the other hand, the presence of BSA in Hanks’ solution increased the rate of biodegradation by decreasing both Zn and |Z| while increasing ECN. Finally, using scanning Kelvin probe force microscopy (SKPFM), we observed an adsorbed nanolayer of BSA with aggregated and fibrillar morphology only in Hanks’ solution, where the electrical surface potential was 52 mV lower than that of the Mg oxide layer.