Zinc (Zn2+) and cadmium (Cd2+) in water pose serious threats to human health and the environment. In search for a more effective treatment technology, we prepared a type of carboxymethyl cellulose (CMC) bridged chlorapatite (CMC-CAP) nanoparticles and tested the material for removal of Zn2+ and Cd2+ from water. CMC macromolecules were attached to CAP by bidentate bridging and hydrogen bonding, preserving the high adsorption capacity of CAP nanoparticles while allowing for easy gravity-separation of the nanoparticles. CMC-CAP showed rapid adsorption kinetics and 22.8% and 11.2% higher equilibrium uptake for Zn2+ and Cd2+, respectively, than pristine CAP. An extended dual-mode isotherm model, which takes into account both sorption and chemical precipitation, provided the best fits to the sorption isotherms, giving a maximum Langmuir sorption capacity of 141.1 mg g−1 for Zn2+ and 150.2 mg g−1 for Cd2+ by CMC-CAP. Na+ at up to 5 mM showed modest effects on the uptake of the heavy metals, while 2–5 mM of Ca2+ exerted notable inhibitive effects. Dissolved organic matter (up to 5 mg L−1 as TOC) inhibited the Zn2+ uptake by 16.5% but enhanced the Cd2+ removal by 8.6%. Material characterizations and surface binding analyses revealed that ion exchange, surface precipitation, and surface complexation were the removal mechanisms for the heavy metals. This study demonstrates stabilizer bridging may serve as a convenient strategy to facilitate water treatment uses of nanoparticles.