We report that design of nanomedicines and nanoparticle-based antimicrobial and antifouling formulations, and assessment of the potential implications of nanoparticle release into the environment require understanding nanoparticle interaction with bacterial surfaces. Here we demonstrate electrostatically driven association of functionalized nanoparticles with lipopolysaccharides of Gram-negative bacterial outer membranes and find that lipopolysaccharide structure influences the extent and location of binding relative to the lipid-solution interface. By manipulating the lipopolysaccharide content in Shewanella oneidensis outer membranes, we observed electrostatically driven interaction of cationic gold nanoparticles with the lipopolysaccharide-containing leaflet. We probed this interaction by quartz crystal microbalance with dissipation monitoring (QCM-D) and second harmonic generation (SHG) using solid-supported lipopolysaccharide-containing bilayers. Association of cationic nanoparticles increased with lipopolysaccharide content, while no association of anionic nanoparticles was observed. The harmonic-dependence of QCM-D measurements suggested that a population of the cationic nanoparticles was held at a distance from the outer leaflet-solution interface of bilayers containing smooth lipopolysaccharides (those bearing a long O-polysaccharide). Additionally, smooth lipopolysaccharides held the bulk of the associated cationic particles outside of the interfacial zone probed by SHG. Lastly, our results demonstrate that positively charged nanoparticles are more likely to interact with Gram-negative bacteria than are negatively charged particles, and this interaction occurs primarily through lipopolysaccharides.