Low fertility is the single most important factor limiting livestock reproductive performance, adversely affecting the cattle industry and causing millions of dollars of economic loss. In the livestock industry, male fertility is of crucial importance for the reproductive performance of livestock. However, there is a lack of reliable biomarkers to predict bull fertility in artificial insemination service. The objective of this study was to identify sperm proteins as biomarkers for bull fertility. To discover candidate sperm quality biomarkers, sperm proteome profiling was conducted in extreme high- and extreme low-fertile bulls selected from a pool of 1000 AI sires with varied fertility. Thirty-two differentially expressed proteins were identified. Among them, high levels of sperm outer dense fiber of sperm tails 2 (ODF2) and post-acrosomal assembly of sperm head protein (PAWP/WBP2NL) represented the most extreme differences in quantity between high- and low-fertility bulls. Protein immunodetection and flow cytometry used to validate these putative fertility markers in a combined cohort of 154 AI sires. Both ODF2 and PAWP correlated significantly with fertility. In conclusion, ODF2 and PAWP can be used to assess semen quality and predict sire fertility.