Background: Transanal endoscopic microsurgery (TEM) represents a choice of treatment in patients with neoplastic lesions in the rectum. When TEM fails, completion total mesorectal excision (cTME) is often required. However, a concern is whether cTME increases the rate of abdominoperineal resections (APR) and is associated with higher risk of incomplete mesorectal fascia (MRF) resection. The aim of this study was to compare outcomes of cTME with primary TME (pTME) in patients with rectal cancer. Methods: This was a nationwide study on all patients with cTME from the Danish Colorectal Cancer Group database between 2005 and 2015. Patients with cTME were compared to patients with pTME after propensity score matching (matching ratio 1:2). Matching variables were age, gender, tumor distance from anal verge, American Society of Anesthesiologists (ASA) score and American Joint Committee on Cancer (AJCC) stage. Results: A total of 60 patients with cTME were compared with 120 patients with pTME. Patients with cTME experienced more intraoperative complications as compared to pTME patients (18.3% vs. 6.7%, p = 0.021). However, there was no difference in the rate of perforations at or near the tumor/previous TEM site (6.7% vs. 2.5%, p = 0.224), conversion to open surgery (p = 0.733) or 30-day morbidity (p = 0.86). On multivariate analysis, cTME was not a risk factor for APR (OR 2.49; 95% CI 0.95–6.56; p = 0.064) or incomplete MRF (OR 1.32; 95% CI 0.48–3.63; p = 0.596). There was no difference in the rate of local recurrence between cTME and pTME (5.2% vs. 4.3%, p = 0.1), distant metastases (6.8% vs. 6.8%, p = 1), or survival (p = 0.081). The mean follow-up time was 6 years. Conclusion: In our study, the largest so far on the subject, we find no difference in postoperative short- or long-term outcomes between cTME and pTME.