Cow’s milk allergy (CMA) is the most common food allergy in infants. This study aimed to identify peptide biomarkers predictive of tolerance in a Spanish population of children with CMA. We investigated specific IgE and IgG4 binding to sequential epitopes of the five major CM allergens (α-s1-, α-s2-, β-, and κ-caseins as well as β-lactoglobulin) using a microarray-based immunoassay. Microarray analysis was performed in 118 patients at baseline and after 6, 18, 30, 42, and 54 months. Most patients tolerated CM at 6 months (40.7%) and 18 months (35.4%). We found significant differences in IgE and IgG4 binding intensity and diversity between allergic and tolerant patients. No differences were observed at baseline. Combining baseline IgE and IgG4 serology variables and peptide microarray analysis results, a predictive model was developed using the XGBoost algorithm to classify tolerance status at different time points. The generated models showed high predictive value at 6 and 30 months with AUCs of 0.883 and 0.833, respectively. Therefore, using IgE and IgG4 antibody-binding peptides at baseline, we generated two models predicting tolerance in children with cow’s milk allergy at 6 and 30 months.