Surface coatings made of hydroxyapatite (HAP) have been proposed to protect marble artworks from dissolution in rain, originated by the aqueous solubility of calcite. However, HAP coatings formed by wet chemistry exhibit incomplete coverage of marble surface, which results in limited protective efficacy. In this study, electrodeposition was explored as a new route to possibly form continuous coatings over the marble surface, leaving no bare areas. Electrodeposition was performed by placing marble samples in poultices containing the electrolyte (an aqueous solution with calcium and phosphate precursors) and the electrodes. The influence of several parameters was investigated, namely the role of the working electrode (cathode or anode), the distance between the marble sample and the working electrode, the deposition conditions (potentiostatic or galvanostatic), the electrolyte composition and concentration, the applied voltage, and time. The coating morphology and composition were assessed by SEM/EDS and FT-IR. The protective ability of the most promising formulations was then evaluated, in all cases comparing electrodeposition with traditional wet synthesis methods. The results of the study suggest that electrodeposition is able to accelerate and improve formation of HAP coatings over the marble surface, even though the obtained protective efficacy is not complete yet.