It is known that the grain size plays a major role in the mechanical properties of magnesium. The aim of the present study is to evaluate its role in long-term corrosion rate. Samples of pure magnesium with grain sizes in the range of 0.9–82 μm are produced through severe plastic deformation and annealing treatments. The mechanical properties are evaluated using tensile tests and the corrosion behavior is evaluated using immersion tests in Hank's solution. A maximum yield stress of ≈150 MPa is observed in the sample with 1.8 μm of grain size and an elongation larger than 25% is observed in the ultrafine-grained sample. Ultrafine- and fine-grained magnesium display uniform corrosion with a decreasing corrosion rate while coarse-grained magnesium displays localized corrosion with an accelerated corrosion rate. A corrosion rate of ≈0.2 mm year−1 is observed in the ultrafine- and fine-grained magnesium. The corrosion product layer of the fine-grained magnesium contains elements absorbed from the media. An analysis of the data in the literature suggests that grain refinement changes the corrosion type from localized to uniform corrosion. The exact relationship between grain size and the corrosion rate remains elusive.