Although nanomaterials facilitate significant technological advancement in our society, their potential impacts on the environment are yet to be fully understood. In this study, two environmentally relevant bacteria, Shewanella oneidensis and Bacillus subtilis, have been used as model organisms to elucidate the molecular interactions between these bacterial classes and Au nanoparticles (AuNPs) with well-controlled and well-characterized surface chemistries: anionic 3-mercaptopropionic acid (MPA), cationic 3-mercaptopropylamine (MPNH2), and the cationic polyelectrolyte poly(allylamine hydrochloride) (PAH). The data demonstrate that cationic, especially polyelectrolyte-wrapped AuNPs, were more toxic to both the Gram-negative and Gram-positive bacteria. The levels of toxicity observed were closely related to the percentage of cells with AuNPs associated with the cell surface as measured in situ using flow cytometry. The NP concentration-dependent binding profiles were drastically different for the two bacteria strains, suggesting the critical role of bacterial cell surface chemistry in determining nanoparticle association, and thereby, biological impact.