The binding of peptides to classical major histocompatibility complex (MHC) class I proteins is the single most selective step in antigen presentation. However, the peptide-binding specificity of cattle MHC (bovine leucocyte antigen, BoLA) class I (BoLA-I) molecules remains poorly characterized. Here, we demonstrate how a combination of high-throughput assays using positional scanning combinatorial peptide libraries, peptide dissociation, and peptide-binding affinity binding measurements can be combined with bioinformatics to effectively characterize the functionality of BoLA-I molecules. Using this strategy, we characterized eight BoLA-I molecules, and found the peptide specificity to resemble that of human MHC-I molecules with primary anchors most often at P2 and P9, and occasional auxiliary P1/P3/P5/P6 anchors. We analyzed nine reported CTL epitopes from <i>Theileria parva</i>, and in eight cases, stable and high affinity binding was confirmed. A set of peptides were tested for binding affinity to the eight BoLA proteins and used to refine the predictors of peptide-MHC binding <i>NetMHC</i> and <i>NetMHCpan</i>. The inclusion of BoLA-specific peptide-binding data led to a significant improvement in prediction accuracy for reported <i>T. parva</i> CTL epitopes. For reported CTL epitopes with weak or no predicted binding, these refined prediction methods suggested presence of nested minimal epitopes with high-predicted binding affinity. The enhanced affinity of the alternative peptides was in all cases confirmed experimentally. This study demonstrates how biochemical high-throughput assays combined with immunoinformatics can be used to characterize the peptide-binding motifs of BoLA-I molecules, boosting performance of MHC peptide-binding prediction methods, and empowering rational epitope discovery in cattle.