In this work, the micro-arc oxidation method is used to fabricate surface-modified complex-structured titanium implant coatings to improve biocompatibility. Depending on the utilized electrolyte solution and micro-arc oxidation process parameters, three different types of coatings (one of them—oxide, another two—calcium phosphates) were obtained, differing in their coating thickness, crystallite phase composition and, thus, with a significantly different biocompatibility. An analytical approach based on X-ray computed tomography utilizing software-aided coating recognition is employed in this work to reveal their structural uniformity. Electrochemical studies prove that the coatings exhibit varying levels of corrosion protection. In vitro and in vivo experiments of the three different micro-arc oxidation coatings prove high biocompatibility towards adult stem cells (investigation of cell adhesion, proliferation and osteogenic differentiation), as well as in vivo biocompatibility (including histological analysis). These results demonstrate superior biological properties compared to unmodified titanium surfaces. The ratio of calcium and phosphorus in coatings, as well as their phase composition, have a great influence on the biological response of the coatings.