Sperm chromatin compaction in the sperm head is achieved when histones are replaced by protamines during spermatogenesis. Haploinsufficiency of the protamine 1 (PRM1) or PRM2 gene causes infertility in mice. However, the published data remain inconclusive about a role of PRM1/2 variants in male infertility and their association with semen parameters. By full sequence analysis, we assessed the frequency of sequence variations in PRM1 and PRM2 in three groups of Caucasian patients with idiopathic teratozoospermia and normal (n = 88) or reduced sperm concentration (n = 83) and in men with a high percentage of normal sperm morphology and normal concentrations (n = 77). Two rare (c.54G>A and c.102G>T) and one common SNP (c.230A>C) were identified in PRM1. In PRM2, some rare heterozygous mutations and the two common intronic SNPs 298G>C and 373C>A were detected. None of the PRM1/2 variants was associated with teratozoospermia or individually with other semen parameters. However, significant linkage disequilibrium was detected between the common SNPs of PRM1 and PRM2 which formed haplotypes. Analysis of the pooled group (n = 248) revealed that homozygous carriers of the common haplotype ACC had a twofold higher sperm concentration and count than men lacking this haplotype, with sperm counts of heterozygotes for ACC being midway between the homozygotes. This markedly decreased sperm output might either be caused by spermatozoa lacking the ACC haplotype not being viable, or subject to negative selection. In addition, a significant deviation from Hardy-Weinberg-Equilibrium of these SNPs might indicate natural selection in favour of the ACC allele which leads to higher sperm output and therefore better fertility. In conclusion, for the first time we describe an association of a common haplotype formed by PRM1 and PRM2 with sperm output in a large group of men.