Background Limited evidence exists on the efficacy of regenerative treatment of peri-implantitis. Material and Methods Subjects receiving antibiotics and surgical debridement were randomly assigned to placement of autogenous bone (AB) or bovine-derived xenograft (BDX) and with placement of a collagen membrane. The primary outcome was evidence of radiographic bone fill and the secondary outcomes included reductions of probing depth (PD) bleeding on probing (BOP) and suppuration. Results Twenty-two subjects were included in the AB and 23 subjects in the BDX group. Statistical analysis failed to demonstrate differences for 38/39 variables assessed at baseline. At 12 months, significant better results were obtained in the BDX group for bone levels (p < 0.001), BOP (p = 0.004), PI (p = 0.003) and suppuration (p < 0.01). When adjusting for number of implants treated per subject, a successful treatment outcome PD = 5.0 mm, no pus, no bone loss and BOP at 1/4 or less sites the likelihood of defect fill was higher in the BDX group (LR: 3.2, 95% CI: 1.010.6, p < 0.05). Conclusions Bovine xenograft provided more radiographic bone fill than AB. The success for both surgical regenerative procedures was limited. Decreases in PD, BOP, and suppuration were observed.