Magnesium alloys with coatings have the potential to be used for bone substitute alter-natives since their mechanical properties are close to those of human bone. However, the surface modification of magnesium alloys to increase the surface biocompatibility and reduce the degradation rate remains a challenge. Here, FHA-Mg scaffolds were made of magnesium alloys and coated with fluorohydroxyapatite (FHA). Human mesenchymal stem cells (hMSCs) were cultured on FHA-Mg scaffolds and cell viability, proliferation, and osteogenic differentiation were investigated. The results showed that FHA-Mg scaffolds display a nano-scaled needle-like structure of aggregated crystallites on their surface. The average Mg2+ concentration in the conditioned media collected from FHA-Mg scaffolds (5.8–7.6 mM) is much lower than those collected from uncoated, Mg(OH)2-coated, and hydroxyapatite (HA)-coated samples (32.1, 17.7, and 21.1 mM, respectively). In addition, compared with hMSCs cultured on a culture dish, cells cultured on FHA-Mg scaffolds demonstrated better proliferation and comparable osteogenic differentiation. To eliminate the effect of osteogenic induction medium, hMSCs were cultured on FHA-Mg scaffolds in culture medium and an approximate 66% increase in osteogenic differentiation was observed three weeks later, indicating a significant effect of the nanostructured surface of FHA-Mg scaffolds on hMSC behaviors. With controllable Mg2+ release and favorable mechanical properties, porous FHA-Mg scaffolds have a great potential in cell-based bone regeneration.