Obesity-related diseases affect half of the global population, and bariatric surgery is one of the few interventions with long-lasting weight loss and cardio-metabolic effects. Here, we investigated the effect of Roux-en-Y gastric bypass surgery on the plasma proteome, hypothesizing that specific proteins or protein patterns may serve as key mediators and markers of the metabolic response. We performed mass spectrometry (MS)-based proteomics on two longitudinal studies encompassing 47 morbidly obese patients, generating quantitative information on more than 1,700 proteins. A global correlation matrix incorporating about 200,000 relationships revealed functional connections between proteins and assigned them to physiological processes. The main classes of significantly altered proteins were markers of systemic inflammation and those involved in lipid metabolism. Our data highlight robust correlative and anti-correlative behaviors of circulating proteins to each other and to clinical parameters. A group of inflammation-related proteins showed distinct inverse relationships to proteins consistently associated with insulin sensitivity.