Plasma electrolytic oxidation (PEO) was performed on a laser surface melting (LSM) modified AZ91 Mg alloy. The effect of LSM pre-treatment on the long-term corrosion resistance of the PEO coated AZ91 alloy was evaluated. Results showed that the LSM pretreatment had a negligible effect on the phase composition and microstructure of the PEO coatings. However, after LSM pretreatment, the long-term corrosion resistance of the PEO coated AZ91 alloy revealed a large enhancement. This was mainly ascribed to the improved corrosion resistance of the substrate resulting from the change of microstructure characteristics induced by the LSM treatment. This provided an alternative approach to improve the long-term corrosion resistance of the PEO coated Mg alloy by appropriate surface modified pretreatment of substrates.