A new modified approach was used to synthesize hydroxyapatite-carbon nanocomposite (HAP-C) by utilizing cement kiln dust (CKD), which is an industrial waste product, as a source of calcium. Calcium from CKD was first chelated using citric acid, and the chelate was transformed into calcium carbonate and carbon by calcination at 450 °C for 1 h, then reacted with ortho-phosphoric acid using a precipitation method, thus serving as a precursor for the formation of HAP-C. Then, HAP-C was calcined at various temperatures for 2 h after it reached the desired temperature at a heating rate of 10 °C/min. By characterizing the adsorbent, the composite was mesoporous, with a negatively charged surface at the operating pH, and an average diameter and length of 10 ± 3.6 nm and 8 ± 2.9 nm, respectively. Quantile regression analysis showed that the removal varies directly with time and dose, and inversely with initial concentration. Removal efficiency reached about 95% and about 80% at 10 ppm initial concentration, 10 min contact time, and a dose of 3.8 g/L, at pH 7 for RB and pH 4 for LV, respectively. Adsorption isotherms followed Sips model as inferred from linear and non-linear regression analysis. Adopting this novel approach in synthesizing HAP-C using a single precursor and a waste raw material reduces the environmental impact and incurred costs associated with the conventional synthesis route, while following the principles of circular economy in converting wastes to value-added products.