Atmospheric pressure plasma (AP) treatment, using an open-air jet of ionized CO2, N2, or air, was applied to AZ91D Mg alloy surfaces to investigate its effects on primer coating adhesion and corrosion resistance. The CO2 and air AP treatments formed an O- and C-rich surface layer (Mg-O-C) consisting of agglomerated nanoparticles and pits with a depth of a few microns and increasing the surface roughness by 6–8 times compared with the reference 600 grit-finished surface. Then, three commercial primers, zinc phosphate (ZnP), chromate-containing epoxy, and MIL23377, were applied on the treated surfaces to evaluate the corrosion resistance associated with the coating adhesion. Microscopic analysis demonstrated stronger interlocking between the primer layer and the nano-/microrough Mg-O-C surface compared to the untreated (600 grit-finished) surfaces, indicating improved coating adhesion and corrosion resistance. Crosscut tests of the MIL23377 primer on the CO2 and air AP-treated surfaces showed the highest level of adhesion, ASTM class 5B. Salt spray corrosion tests showed that after 8 days of exposure, the primer coatings on air AP-treated surfaces had corrosion areas that were more than four times smaller than that of the 600 grit-finished surface. The N2 AP treatment showed similar adhesion enhancement. The preliminary operation expenses for AP treatment using CO2, N2, and air were estimated at USD 30.62, USD 35.45, and USD 29.75 (from an air cylinder)/USD 0.66 (from an air compressor) per m2, respectively.