Heteroaggregation of nanoparticles with naturally occurring colloids has been shown to be an important process in nanoparticle fate and transport in the aquatic environment. The advent of a functional assay to measure heteroaggregation attachment efficiencies has opened the door for further mechanistic studies. It is well known that natural organic matter (NOM) will adsorb to and coat natural colloids and nanoparticles, affecting their colloidal stability. Here, the aggregation of silicon dioxide beads with branched polyethylenimine-coated gold nanoparticles in the presence of Suwanee River Natural Organic Matter was studied. The surface coverage of the natural organic matter on the nanoparticles was found to vary with the ratio of the NOM concentration to the nanoparticle surface area. This surface coverage was found to affect the heteroaggregation attachment efficiencies between the nanoparticles and beads. This necessitates the use of environmentally relevant ratios of NOM and nanoparticles when designing laboratory experiments to determine heteroaggregation attachment efficiencies. A model was developed to explain how heteroaggregation attachment efficiencies change with surface coverages and the affinities between the covered/uncovered surfaces of nanoparticles and the covered/uncovered surfaces of natural colloids.