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 Theileria parva, 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 NetMHC and NetMHCpan. The inclusion of BoLA-specific peptide-binding data led to a significant improvement in prediction accuracy for reported T. parva 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.