Purpose: We aimed to investigate the development of common procedures used as treatment for rectal prolapse over a decade and to determine if the choice of primary operation affects the reoperation rate. Methods: This is a retrospective analysis of operative data from a National Data Registry, Landspatientregisteret (LPR), from the period of January 1, 2004 to December 31, 2014. All hospitalized surgical treatments are registered in LPR. Results: Sixteen hundred and twenty-five patients with rectal prolapse underwent 1834 operations. There were 94% women and mean age at surgery was 71.6 ± 18.1 years, with no difference over the 11 years. The types of operations performed differed (p < 0.0001), with an increase in overall number of operations and increasing use of laparoscopic procedures. There were 209 reoperations, of which 129 patients were primarily operated with a perineal procedure. The mean age at reoperation was 72.8 ± 17.3 years. The most frequently used reoperation was laparoscopic rectopexy. The overall reoperation rate was 16%: 10% for both open and laparoscopic rectopexy, and for perineal procedures 26% (p < 0.001). The overall 30-day mortality was 2.1% and there was no difference in mortality between the procedures (p = 0.23). Conclusions: The overall number of rectal prolapse operations was increasing. There was a clear trend towards extended use of laparoscopic rectopexy both as primary procedure and as reoperation. The highest reoperation rates were for the perineal procedures.