Bacterial infection of in-dwelling medical devices is a growing problem that cannot be treated by traditional antibiotics due to the increasing prevalence of antimicrobial resistance and biofilm formation. Here, due to changes in surface parameters, it is proposed that bacterial adhesion can be prevented through nanosurface modifications of the medical device alone. Toward this goal, titanium was created to possess nanotubular surface topographies of highly controlled diameters of 20, 40, 60, or 80 nm, sometimes followed by heat treatment to control chemistry and crystallinity, through a novel anodization process. For the first time it was found that through the control of Ti surface parameters including chemistry, crystallinity, nanotube size, and hydrophilicity, significantly changed responses of both Staphylococcus epidermidis and Staphylococcus aureus (pathogens relevant for orthopaedic and other medical device related infections) were measured. Specifically, heat treatment of 80 nm diameter titanium tubes produced the most robust antimicrobial effect of all surface treatment parameters tested. This study provides the first step toward understanding the surface properties of nano-structured titanium that improve tissue growth (as has been previously observed with nanotubular titanium), while simultaneously reducing infection without the use of pharmaceutical drugs.