Purpose: Post-treatment follow-up in women with cervical pre-cancers (CIN3) is mandatory due to relapse in up to 10% of patients. Standard follow-up based on hrHPV-DNA/cytology co-testing has high sensitivity but limited specificity. The aim of our prospective, multicenter, observational study was to test the hypothesis that an individualized viral-cellular-junction test (vcj-PCR) combined with cytology has a lower false positive rate for the prediction of recurrence compared to standard co-testing. Methods: Pre-surgical cervical swabs served for the identification of HPV16/18 DNA integration sites by next-generation-sequencing (NGS). Samples taken at 6, 12 and 24 months post-surgery were evaluated by cytology, hrHPV-DNA and the patients’ individual HPV-integration sites (vcj-PCR on the basis of NGS). Results: Integration sites were detected in 48 of 445 patients (10.8%), 39 of them had valid follow-up data. The false positive rate was 18.2% (95% CI 8.6–34.4%) for standard hrHPV/cytology at six months compared to 12.1% (95% CI 4.8–27.3%) for vcj-PCR/cytology, respectively (McNemar p = 0.50). Six patients developed recurrences (1 CIN2, 5 CIN3) during follow-up. Standard co-testing detected all, whereas vcj-PCR/cytology detected only five patients with recurrences. Data of 269 patients without evidence of HPV16/18 integration were subject to post-hoc analyses. Standard co-testing revealed a false positive rate of 15.7% (95% CI 11.7–20.7%) and predicted ten of fourteen recurrences at six months. Conclusions: Although highly specific on its own vcj-PCR could not detect all recurrent CIN2/3. Possible reasons for this unexpected result may be multifocal lesions, intratumoral heterogeneity with respect to HPV integration and/or incident CIN.