Sperm cryopreservation preserves genetic resources for animal breeding and for human patients who suffers from permanent testicular damage. Although the sperm cryopreservation has been used for many years, the addition of cryoprotective agent (CPA) during cryopreservation negatively affects sperm function and quality. Our previous study reported that the addition of CPA reduced bull sperm physiological functions. However, the sperm cells collected from individual bulls presented different sensitivity to the damage induced by CPA. In the present study, we examined if CPA affect sperm cells acquired from individual bulls. Individual bull spermatozoa were divided into two groups based on motility parameters; high CPA-tolerant sperm (HCS) and low CPA-tolerant sperm (LCS). Our results showed that the HCS group presented good physiological function after CPA exposure, whereas the LCS group showed a significant decrease in the sperm function. We also found differentially expressed five proteins between the HCS and LCS groups, which refer to cytosolic 5′-nucleotidase 1B (NT5C1B), fumarate hydratase (FH), F-actin-capping protein subunit beta (CAPZB), voltage-dependent anion-selective channel protein 2 (VDAC2), and cytochrome b-c1 complex subunit 1 (UQCRC1). NT5C1B and FH showed abundant expression in the HCS group, while the expression of CAPZB, VDAC2, and UQCRC1 was relatively lower in the HCS group than in the LCS group. The current results suggest that NT5C1B, FH, CAPZB, VDAC2, and UQCRC1 can be used as potential markers to predict CPA-tolerable spermatozoa. Those markers provide a reliable tool to select animals and breeds with CPA tolerance.