Heteroaggregation with clay mineral particles (CMPs) is significant to the environmental application and fate of increasingly produced nanoparticulate zero-valent iron (nZVI). Co-settling, kinetic aggregation, calculation of the classical Derjaguin–Landau–Verwey–Overbeek interaction energy, and electron microscopic observation were carried out to investigate the interaction between nZVIs (three naked nZVIs of different sizes and one carboxymethyl cellulose (CMC) coated nZVI) and CMPs (kaolinite and montmorillonite). Under pH 6.5 and 9.5 conditions, Lewis acid–base interaction contributed to the attachment between nZVIs and CMPs, while electrostatic attraction was involved in nZVI–CMP attachment under pH 3.5. Compared with the heteroaggregates formed by nZVIs attaching to CMP edges and faces under pH 6.5 and 3.5 conditions, the heteroaggregates were smaller with nZVIs mainly connecting to CMP edges under pH 9.5. Small nZVI homoaggregates were bound to CMP edges at low nZVI concentrations (nZVI/CMP mass ratio at 0.015) with CMP concentrations of 330 mg L−1 and large nZVI–CMP heteroaggregates formed by nZVI bridging with increasing nZVI concentrations. The smallest nZVI exhibited the strongest heteroaggregation with CMPs; the CMC coating inhibited the interfacial interaction and heteroaggregation between nZVIs and CMPs; kaolinite had higher potential to interact with nZVIs under neutral conditions. These findings are helpful for understanding the interaction between nZVIs and minerals and of significance to environmental remediation using nZVIs.