Mg has received much attention as a next-generation implantable material owing to its biocompatibility, bone-like mechanical properties, and biodegradability in physiological environments. The application of various polymer coatings has been conducted in the past to reduce the rapid formation of hydrogen gas and the local change in pH during the initial phase of the chemical reaction with the body fluids. Here, we propose femtosecond (fs) laser-mediated Mg surface patterning for significant enhancement of the binding strength of the coating material, which eventually reduces the corrosion rate. Analyses of the structural, physical, crystallographic, and chemical properties of the Mg surface have been conducted in order to understand the mechanism by which the surface adhesion increases between Mg and the polymer coating layer. Depending on the fs laser conditions, the surface structure becomes rough owing to the presence of several microscaled pits and grooves of nanoporous MgO, resulting in a tightly bonded poly(lactic-co-glycolic acid) (PLGA) layer. The corrosion rate of the PLGA-coated, fs laser-treated Mg is considerably slow compared with the non-treated Mg; the treated Mg is also more biocompatible compared with the non-treated Mg. The fs laser-based surface modification technique offers a simple and quick method for introducing a rough coating on Mg; further, it does not require any chemical treatment, thereby overcoming a potential obstacle for its clinical use.