Background: Colorectal cancer (CRC) is the fourth most commonly diagnosed and third most deadly cancer worldwide. Surgery is the main treatment option for early disease; however, a relevant proportion of CRC patients relapse. Here, variations among preoperative and postoperative serum metabolomic fingerprint of CRC patients were studied, and possible associations between metabolic variations and cancer relapse were explored. Methods: A total of 41 patients with stage I-III CRC, planned for radical resection, were enrolled. Serum samples, collected preoperatively (t0) and 4–6 weeks after surgery before the start of any treatment (t1), were analyzed via NMR spectroscopy. NMR data were analyzed using multivariate and univariate statistical approaches. Results: Serum metabolomic fingerprints show differential clustering between t0 and t1 (82–85% accuracy). Pyruvate, HDL-related parameters, acetone, and 3-hydroxybutyrate appear to be the major players in this discrimination. Eight out of the 41 CRC patients enrolled developed cancer relapse. Postoperative, relapsed patients show an increase of pyruvate and HDL-related parameters, and a decrease of Apo-A1 Apo-B100 ratio and VLDL-related parameters. Conclusions: Surgery significantly alters the metabolomic fingerprint of CRC patients. Some metabolic changes seem to be associated with the development of cancer relapse. These data, if validated in a larger cohort, open new possibilities for risk stratification in patients with early-stage CRC.