So-called Prussian Blue Analogues (PBAs) attract significant research interest for a large variety of electrochemical applications. Recently, they have been recognized as promising electrode materials to implement in aqueous Na-ion batteries for grid-scale energy storage systems. Further types of aqueous batteries using, for instance, alkali metal cations such as Li+ and K+ or multivalent ions like Mg2+, Zn2+ and Al3+ as insertion species for PBA-based electrodes are being explored. In this study we systematically investigate intercalation of Mg2+ into four electrodeposited PBA thin films: Na2Ni[Fe(CN)6], Na2Co[Fe(CN)6], Na2VOx[Fe(CN)6], and NaIn[Fe(CN)6]. All four electrodes are capable of hosting Mg2+, while NaIn[Fe(CN)6] shows better stability upon repeated (dis)charging compared to the other three systems. Surprisingly, even though the hydration energies of Na+ and Mg2+ differ significantly, the mean half-charge potentials of (de)intercalation are comparable for both cations. A correlation between the empirical radii of transition metals present in the structure of PBAs and the mean half-charge potential of (de)intercalation, previously identified for Na+, is also found for Mg2+.