Centrioles are evolutionarily conserved microtubule-based structures at the core of the animal centrosome that are essential for nucleating the axoneme of cilia. We hypothesized that centriole proteins have been under-represented in proteomic studies of the centrosome, because of the larger amount of pericentriolar material making up the centrosome. In this study, we have overcome this problem by determining the centriolar proteome of mammalian sperm cells, which have a pair of centrioles but little pericentriolar material. Mass spectrometry of sperm centrioles identifies known components of centrioles and many previously uncharacterized candidate centriole proteins. Assessment of localization of a subset of these candidates in cultured cells identified CCDC113, CCDC96, C4orf47, CCDC38, C7orf31, CCDC146, CCDC81 and CCDC116 as centrosome-associated proteins. We examined the highly conserved protein CCDC113 further and found that it is a component of centriolar satellites, is in a complex with the satellite proteins HAP1 and PCM1, and functions in primary cilium formation.