Background: The microbiome of the male urogenital tract is poorly described but it has been suggested that bacterial colonization of the male urethra might impact risk of sexually transmitted infection (STI). Previous cultivation-dependent studies showed that a variety of non-pathogenic bacteria colonize the urethra but did not thoroughly characterize these microbiomes or establish links between the compositions of urethral microbiomes and STI. Methodology/Findings: Here, we used 16S rRNA PCR and sequencing to identify bacteria in urine specimens collected from men who lacked symptoms of urethral inflammation but who differed in status for STI. All of the urine samples contained multiple bacterial genera and many contained taxa that colonize the human vagina. Uncultivated bacteria associated with female genital tract pathology were abundant in specimens from men who had STI. Conclusions: Urine microbiomes from men with STI were dominated by fastidious, anaerobic and uncultivated bacteria. The same taxa were rare in STI negative individuals. Our findings suggest that the composition of male urine microbiomes is related to STI. © 2010 Nelson et al.