Background: The environmental factors for promoting prostate cancer (PCa) recurrence remain unknown. Methods: A retrospective cross-sectional study was conducted in healthy men (n = 12) and PCa patients undergoing prostatectomy (n = 27). Plasma preoperative level of total cell-free bacterial 16S rDNA, a marker of microbial translocation, was evaluated by qPCR. Plasma levels of prostate-specific antigen (PSA) were evaluated by ELISA. Results: Similar degrees of microbial translocation were found in healthy men and patients. However, the levels of microbial 16S rDNA were increased in patients with cancer relapse (n = 10) compared to patients without relapse (n = 17) after prostatectomy. Furthermore, the levels of microbial 16S rDNA were marginally increased in patients with pT3 or pT4 tumors compared to those with pT 2 or less. The levels of microbial 16S rDNA tended to increase in patients with higher pathologic tumor stage, Gleason score, and margin and lymph node involvements; but these differences did not reach significance. Conclusion: The plasma 16S rDNA levels increased in patients with PCa who have biochemical recurrence and 16S rDNA levels were higher in patients with higher-grade PCa.