Background: Bone grafting is an important surgical procedure to reconstruct alveolar bone defects in patients with cleft lip and palate. Polyphosphate (PolyP) is a physiological polymer present in the blood, primarily in platelets. PolyP plays a role as a phosphate source in bone calcium phosphate deposition. Moreover, the cleavage of high-energy bonds to release phosphates provides local energy necessary for regenerative processes. In this study, polyP is complexed with calcium to form Calcium polyP microparticles (Ca-polyP MPs), which were shown to have osteoinductive properties in preclinical studies. The aim of this study was to evaluate the feasibility, safety, and osteoinductivity of Ca-polyP MPs, alone or in combination with BCP, in a first-in-human clinical trial. Methods: This single-blinded, parallel, prospective clinical pilot study enrolled eight adolescent patients (mean age 18.1: range 13–34 years) with residual alveolar bone cleft. Randomization in two groups (four receiving Ca-polyP MPs only, four a combination of Ca-polyP MPs and biphasic calcium phosphate (BCP)) was performed. Patient follow-up was 6 months. Outcome parameters included safety parameters and close monitoring of possible adverse effects using radiographic imaging, regular blood tests, and physical examinations. Osteoinductivity evaluation using histomorphometric analysis of biopsies was not possible due to COVID restrictions. Results: Due to surgical and feasibility reasons, eventually, only 2 patients received Ca-polyP MPs, and the others the combination graft. All patients were assessed up to day 90. Four out of eight were able to continue with the final assessment day (day 180). Three out of eight were unable to reach the hospital due to COVID-19 restrictions. One patient decided not to continue with the study. None of the patients showed any allergic reactions or any remarkable local or systematic side effects. Radiographically, patients receiving Ca-polyP MPs only were scored grade IV Bergland scale, while patients who got the BCP/Ca-polyP MPs combination had scores ranging from I to III. Conclusions: Our results indicate that Ca-polyP MPs and the BCP/Ca-polyP MPs combination appear to be safe graft materials; however, in the current setting, Ca-polyP MPs alone may not be a sufficiently stable defect-filling scaffold to be used in alveolar cleft repair. Trial registration: Indonesian Trial Registry under number INA-EW74C1N by the ethical committee of Faculty of Medicine, Hasanuddin University, Makassar, Indonesia with code number 1063/UN184.108.40.206.31/PP36/2019.