Background: Many people struggle with the choice in a series of processes, from prostate cancer (PCa) diagnosis to treatment. We investigated the degree of regret after the prostate biopsy (PBx) and relevant factors in patients recommended for biopsy for suspected PCa. Methods: From 06/2020 to 05/2022, 198 people who performed PBx at three institutions were enrolled and analyzed through a questionnaire before and after biopsy. Before the biopsy, a questionnaire was conducted to evaluate the sociodemographic information, anxiety scale, and health literacy, and after PBx, another questionnaire was conducted to evaluate the decision regret scale. For patients diagnosed as PCa after biopsy, a questionnaire was conducted when additional tests were performed at PCa staging work-up. Results: 190 patients answered the questionnaire before and after PBx. The mean age was 66.2 ± 7.8 years. Overall, 5.5% of men regretted biopsy, but there was no significant difference between groups according to the PCa presence. Multivariate analysis, to identify predictors for regret, revealed that the case when physicians did not properly explain what the prostate-specific antigen (PSA) test was like and what PSA elevation means (OR 20.57, [95% CI 2.45–172.70], p = 0.005), low media literacy (OR 10.01, [95% CI 1.09–92.29], p = 0.042), and when nobody to rely on (OR 8.49, [95% CI 1.66–43.34], p = 0.010) were significantly related. Conclusions: Overall regret related to PBx was low. Decision regret was more significantly related to media literacy rather than to educational level. For patients with relatively low media literacy and fewer people to rely on in case of serious diseases, more careful attention and counseling on PBx, including a well-informed explanation on PSA test, is helpful.