Serum components of sepsis patients vary with the severity of infection, the resulting inflammatory response, per individual, and even over time. Tracking these changes is crucial in properly treating sepsis. Hence, several blood-derived biomarkers have been studied for their potential in assessing sepsis severity. However, the classical approach of selecting individual biomarkers is problematic in terms of accuracy and efficiency. We therefore present a novel approach for detecting biomarkers using longitudinal proteomics data. This does not require a predetermined set of proteins and can therefore reveal previously unknown related proteins. Our approach involves examining changes over time of both protein abundance and post-translational modifications in serum, using two-dimensional gel electrophoresis (2D-PAGE). 2D-PAGE was conducted using serum from n = 20 patients, collected at five time points, starting from the onset of sepsis. Changes in protein spots were examined using 49 spots for which the signal intensity changed by at least two-fold over time. These were then screened for significant spikes or dips in intensity that occurred exclusively in patients with adverse outcome. Individual level variation was handled by a mixed effects model. Finally, for each time transition, partial correlations between spots were estimated through a Gaussian graphical model (GGM) based on the ridge penalty. Identifications of spots of interest by tandem mass spectrometry revealed that many were either known biomarkers for inflammation (complement components), or had previously been suggested as biomarkers for kidney failure (haptoglobin) or liver failure (ceruloplasmin). The latter two are common complications in severe sepsis. In the GGM, many of the tightly connected spots shared known biological functions or even belonged to the same protein; including hemoglobin chains and acute phase proteins. Altogether, these results suggest that our screening method can successfully identify biomarkers for disease states and cluster biologically related proteins using longitudinal proteomics data derived from 2D-PAGE.