Our recent studies suggested that the freezability of carp semen is related to seminal plasma protein profiles. Here, we aimed to compare the spermatozoa proteomes of good (GF) and poor (PF) freezability semen of carp. To achieve this, we used two-dimensional difference in gel electrophoresis followed by MALDI-TOF/TOF mass spectrometry. The semen was classified as GF or PF based on sperm motility after freeze/thawing. We identified proteins enriched in spermatozoa of GF (22 proteins) and PF (18 proteins) semen. We also identified 12 proteins enriched in the supernatant after cryopreservation of PF semen. Good freezability is related to high concentrations of proteins involved in the maintenance of flagella structure, membrane fluidity, efficient control of Ca2+ and sperm motility, energy production, and antioxidative protection, which likely reflects the full maturation status of spermatozoa of GF semen. On the other hand poor freezability seems to be related to the presence of proteins identified as released in high quantities from cryopreserved sperm of PF. Thus, the identified proteins might be useful bioindicators of freezing resilience and could be used to screen carp males before cryopreservation, thus improve long-term sperm preservation in carp.