Background: Previous studies of the outcome after perineal stapled prolapse resection (PSPR) have included a limited number of patients with a short follow-up and high recurrence rates. The present study was designed to assess the initial results, complications, recurrence rate, and outcomes up to 4 years after PSPR, as well as the need for a repeated procedure. Methods: Fifty-four consecutive patients with rectal prolapse (mean age 77.2 years, range 46–93 years; n = 3 men) were selected for PSPR between May 2009 and February 2015. Prolapse length was measured at baseline and after surgery. Patients were asked to grade intensity of symptoms as a satisfaction score of 1–10, 10 representing being symptom-free. Results: The mean operation time was 45.3 min (SD = 17.5, range 25–95 min). The mean rectal prolapse length was reduced significantly from 9.5 cm (SD = 5.0, range 4–30 cm) to 1.2 cm (SD = 2.6, range 0–10 cm; p < 0.0001). Bleeding requiring surgical intervention occurred in two patients (3.7%). Postoperative satisfaction score increased from a mean of 2.2 (SD = 0.9) to a mean of 6.4 (SD = 2.8, p ≤ 0.0001). After a mean follow-up of 13.4 months (SD = 14.1), six patients with recurrence underwent a new PSPR and five patients underwent colostomy, mainly because of incontinence, resulting in a recurrence rate of 20.4%. There were no complications after redo PSPR, and after a median of 10-month follow-up (range 6–37), there were no recurrences. Conclusions: PSPR is a rather new surgical procedure for external rectal prolapse. Immediate complications are few and not serious. Although recurrences can be treated with a second PSPR, the operation may only be the best option for old and fragile patients with comorbidities and a short life expectancy.