Biodegradable implants are critical for regenerative orthopaedic procedures, but they may suffer from too fast corrosion in human-body environment. This necessitates the synthesis of a suitable coating that may improve the corrosion resistance of these implants without compromising their mechanical integrity. In this study, an AZ91 magnesium alloy, as a representative for a biodegradable Mg implant material, was modified with a thin reduced graphene oxide (RGO)-calcium carbonate (CaCO3) composite coating. Detailed analytical and in-vitro electrochemical characterization reveals that this coating significantly improves the corrosion resistance and mechanical integrity, and thus has the potential to greatly extend the related application field.