Some articles have revealed that the electrodeposition of calcium phosphate (CaP) coatings entails a precursor phase, similarly to biomineralization in vivo. The chemical composition of the initial layer and its thickness are, however, still arguable, to the best of our knowledge. Moreover, while CaP and electrodeposition of metal coatings have been studied utilizing atom-probe tomography (APT), the electrodeposition of CaP ceramics has not been heretofore studied. Herein, we present an investigation of the CaP deposition on a gold substrate. Using APT and transmission electron microscopy (TEM) it is found that a mixture of phases, which could serve as transient precursor phases to hydroxyapatite (HAp), can be detected. The thickness of these phases is tens of nanometers, and they consist of amorphous CaP (ACP), dibasic calcium phosphate dihydrate (DCPD), and octacalcium phosphate (OCP). This demonstrates the value of using atomic-resolved characterization techniques for identifying the precursor phases. It also indicates that the kinetics of their transformation into the more stable HAp is not too fast to enable their observation. The coating gradually displays higher Ca/P atomic ratios, a porous nature, and concomitantly a change in its density.