Shooting activities are a very important source of contamination as they are commonly detected high concentrations of Pb in the soils from these facilities. Different remediation methods imply the immobilization of the pollutants by decreasing their mobility and availability and nanotechnology is a promising technique in this field. The effectiveness of calcium phosphate nanoparticles (CPNs) in the remediation of small-arms firing range and trap shooting range soils is evaluated in this work. The operationally defined extractable content of Pb, Cu and Zn is determined together with the interaction of the pollutants with the nanomaterials. Soil samples were treated with the CPNs and after the treatment the extractable contents of Cu, Pb and Zn decrease. To check the retention by the nanoparticles TOF-SIMS (Time of Flight Secondary Ion Mass Spectrometry) and HR-TEM-EDS (High Resolution Transmission Electron Microscopy with Energy Dispersive X-ray Spectroscopy) techniques were applied. The association of Pb and Cu to the CPNs was demonstrated by TOF-SIMS although it also indicated that not all the Pb and Cu contents are linked to the nanoparticles. By means of HR-TEM/EDS it was made out the filamentous shape and the size (50–150 nm long and 20–40 nm wide) of the CPNs together with their elemental composition (Ca, P and O). The CPNs were identified in treated soil samples together with signals of metals. The decrease on metal extractability detected is, in part, due to the association with CPNs but still more investigation is needed regarding mobility and availability of potentially hazardous elements in soils treated with nanoparticles.