Male infertility is a long-standing enigma of significant medical concern. The integrity of sperm chromatin is a clinical indicator of male fertility and in vitro fertilization potential: chromosome aneuploidy and DNA decondensation or damage are correlated with reproductive failure. Identifying conserved proteins important for sperm chromatin structure and packaging can reveal universal causes of infertility. Here we combine proteomics, cytology and functional analysis in Caenorhabditis elegans to identify spermatogenic chromatin-associated proteins that are important for fertility. Our strategy employed multiple steps: purification of chromatin from comparable meiotic cell types, namely those undergoing spermatogenesis or oogenesis; proteomic analysis by multidimensional protein identification technology (MudPIT) of factors that co-purify with chromatin; prioritization of sperm proteins based on abundance; and subtraction of common proteins to eliminate general chromatin and meiotic factors. Our approach reduced 1,099 proteins co-purified with spermatogenic chromatin, currently the most extensive catalogue, to 132 proteins for functional analysis. Reduction of gene function through RNA interference coupled with protein localization studies revealed conserved spermatogenesis-specific proteins vital for DNA compaction, chromosome segregation, and fertility. Unexpected roles in spermatogenesis were also detected for factors involved in other processes. Our strategy to find fertility factors conserved from C. elegans to mammals achieved its goal: of mouse gene knockouts corresponding to nematode proteins, 37% (7/19) cause male sterility. Our list therefore provides significant opportunity to identify causes of male infertility and targets for male contraceptives.