To evaluate the presence of serum protein biomarkers associated with the early phases of formation of carotid atherosclerotic plaques, label-free quantitative proteomics analyses were made for serum samples collected as part of The Cardiovascular Risk in Young Finns Study. Samples from subjects who had an asymptomatic carotid artery plaque detected by ultrasound examination (N = 43, Age = 30–45 years) were compared with plaque free controls (N = 43) (matched for age, sex, body weight and systolic blood pressure). Seven proteins (p < 0.05) that have been previously linked with atherosclerotic phenotypes were differentially abundant. Fibulin 1 proteoform C (FBLN1C), Beta-ala-his-dipeptidase (CNDP1), Cadherin-13 (CDH13), Gelsolin (GSN) and 72 kDa type IV collagenase (MMP2) were less abundant in cases, whereas Apolipoproteins C-III (APOC3) and apolipoprotein E (APOE) were more abundant. Using machine learning analysis, a biomarker panel of FBLN1C, APOE and CDH13 was identified, which classified cases from controls with an area under receiver-operating characteristic curve (AUROC) value of 0.79. Furthermore, using selected reaction monitoring mass spectrometry (SRM-MS) the decreased abundance of FBLN1C was verified. In relation to previous associations of FBLN1C with atherosclerotic lesions, the observation could reflect its involvement in the initiation of the plaque formation, or represent a particular risk phenotype.