Bacterial infection of implants and prosthetic devices is one of the most common causes of implant failure. The nanostructured surface of biocompatible materials strongly influences the adhesion and proliferation of mammalian cells on solid substrates. The observation of this phenomenon has led to an increased effort to develop new strategies to prevent bacterial adhesion and biofilm formation, primarily through nanoengineering the topology of the materials used in implantable devices. While several studies have demonstrated the influence of nanoscale surface morphology on prokaryotic cell attachment, none have provided a quantitative understanding of this phenomenon. Using supersonic cluster beam deposition, we produced nanostructured titania thin films with controlled and reproducible nanoscale morphology respectively. We characterized the surface morphology; composition and wettability by means of atomic force microscopy, X-ray photoemission spectroscopy and contact angle measurements. We studied how protein adsorption is influenced by the physico-chemical surface parameters. Lastly, we characterized Escherichia coli and Staphylococcus aureus adhesion on nanostructured titania surfaces. Our results show that the increase in surface pore aspect ratio and volume, related to the increase of surface roughness, improves protein adsorption, which in turn downplays bacterial adhesion and biofilm formation. As roughness increases up to about 20 nm, bacterial adhesion and biofilm formation are enhanced; the further increase of roughness causes a significant decrease of bacterial adhesion and inhibits biofilm formation. We interpret the observed trend in bacterial adhesion as the combined effect of passivation and flattening effects induced by morphology-dependent protein adsorption. Our findings demonstrate that bacterial adhesion and biofilm formation on nanostructured titanium oxide surfaces are significantly influenced by nanoscale morphological features. The quantitative information, provided by this study about the relation between surface nanoscale morphology and bacterial adhesion points towards the rational design of implant surfaces that control or inhibit bacterial adhesion and biofilm formation.