Background: Various conditions with cellular decay are associated with elevated cell-free DNA (cfDNA). This study aimed to investigate if perioperatively measured cfDNA levels were associated with the surgical approach, complications, or recurrence. Methods: Plasma was obtained from patients who underwent surgery for colon cancer at admission and at the time of discharge. Quantitative measurement of cfDNA was performed by amplifying two amplicons of 102 base pairs (bp) and 132 bp of Beta-2-Microglobulin (B2M) and Peptidyl-Prolyl cis–trans Isomerase A (PPIA), respectively. Results: cfDNA was measured in 48 patients who underwent surgery for colonic cancer. Sixteen patients had recurrence during the follow-up period, fifteen developed a postoperative complication, and seventeen patients developed neither, acting as the control group. Postoperative cfDNA levels were significantly elevated from baseline samples, across all groups, with a median preoperatively B2M level of 48.3 alleles per mL and postoperatively of 220 alleles per mL and a median preoperatively level PPIA of 26.9 alleles per mL and postoperatively of 111.6 alleles per mL (p < 0.001 for B2M and p < 0.001 for PPIA). Postoperative levels of PPIA, but not B2M, were significantly higher in patients experiencing complications than in the control group (p = 0.036). However, a tendency towards an association between the surgical approach and the changes in cfDNA levels was found for PPIA (p = 0.058), and B2M (p = 0.087). Conclusions: Plasma cfDNA was increased after surgery in all patients with colon cancer. Postoperative PPIA levels were significantly higher in patients experiencing surgical complications but not in B2M levels.