Background: The role of a collagen plug for treating anal fistula is not well established. A randomized prospective multicentre non-inferiority study of surgical treatment of trans-sphincteric cryptogenic fistulas was undertaken, comparing the anal fistula plug with the mucosal advancement flap with regard to fistula recurrence rate and functional outcome. Methods: Patients with an anal fistula were evaluated for eligibility in three centres, and randomized to either mucosal advancement flap surgery or collagen plug, with clinical follow-up at 3 and 12 months. The primary outcome was the fistula recurrence rate. Anal pain (visual analogue scale), anal incontinence (St Marks score) and quality of life (Short Form 36 questionnaire) were also reported. Results: Ninety-four patients were included; 48 were allocated to the plug procedure and 46 to advancement flap surgery. The median follow-up was 12 (range 9-24) months. The recurrence rate at 12 months was 66 per cent (27 of 41 patients) in the plug group and 38 per cent (15 of 40) in the flap group (P = 0.006). Anal pain was reduced after operation in both groups. Anal incontinence did not change in the follow-up period. Patients reported an increased quality of life after 3 months. There were no differences between the groups with regard to pain, incontinence or quality of life. Conclusion: There was a considerably higher recurrence rate after the anal fistula plug procedure than following advancement flap repair.