18F-labeled prostate-specific membrane antigen (PSMA) PET tracers are increasingly used in preference to 68Ga-PSMA-11 for restaging biochemical recurrence (BCR) of prostate cancer. They are associated with longer half-lives, larger-scale production, and lower positron range than their 68Ga-labeled counterparts. Here, we describe the efficacy of an 18F-labeled radiohybrid PSMA, rhPSMA-7, a novel theranostic PSMA-targeting agent for imaging BCR of prostate cancer. Methods: Datasets from 261 consecutive patients with noncastrate BCR after radical prostatectomy who underwent 18F-rhPSMA-7 PET/CT at our institution between June 2017 and March 2018 were reviewed retrospectively. All lesions suspected of being recurrent prostate cancer were recorded. The detection rate for sites of presumed recurrence was correlated with patients' prostate-specific antigen (PSA) level, primary Gleason score, and prior therapy (androgen deprivation therapy and external-beam radiation therapy). Results: The 261 patients had a median PSA level of 0.96 ng/mL (range, 0.01-400 ng/mL). The median injected activity of 18F-rhPSMA-7 was 336 MBq, with a median uptake time of 76 min. In total, 211 patients (81%) showed pathologic findings on 18F-rhPSMA-7 PET/CT. The detection rates were 71% (42/59), 86% (44/51), 86% (42/49), and 95% (76/80) at PSA levels of 0.2 to <0.5 ng/mL, 0.5 to <1 ng/mL, 1 to <2 ng/mL, and ≥2 ng/mL, respectively. In 32% patients (7/22) with a PSA of less than 0.2 ng/mL, suggestive lesions were present. 18F-rhPSMA-7 PET/CT revealed local recurrence in 43% of patients (113). Lymph node metastases were present in the pelvis in 42% of patients (110), in the retroperitoneum in 17% (45), and in a supradiaphragmatic location in 8.0% (21). Bone and visceral metastases were detected in 21% (54) and 3.8% (10), respectively. Detection efficacy was not influenced by prior external-beam radiation therapy (79.1% vs. 82.1%, P = 0.55), androgen deprivation therapy within the 6 mo preceding imaging (80.6% vs. 80.9%, P = 0.54), or primary Gleason score (77.9% for ≤7 vs. 82.6% for ≥8, P = 0.38). Conclusion:18F-rhPSMA-7 PET/CT offers high detection rates in early BCR after radical prostatectomy, especially among patients with low PSA values.