Nanos is one of the evolutionarily conserved proteins implicated in germ cell development and we have previously shown that it interacts with the CCR4-NOT deadenylation complex leading to the suppression of specific RNAs. However, the molecular mechanism and physiological significance of this interaction have remained elusive. In our present study, we identify CNOT1, a component of the CCR4-NOT deadenylation complex, as a direct factor mediating the interaction with NANOS2. We find that the first 10 amino acids (AAs) of NANOS2 are required for this binding. We further observe that a NANOS2 mutant lacking these first 10 AAs (NANOS2-ΔN10) fails to rescue defects in the Nanos2-null mouse. Our current data thus indicate that the interaction with the CCR4-NOT deadenylation complex is essential for NANOS2 function. In addition, we further demonstrate that NANOS2-ΔN10 can associate with specific mRNAs as well as wild-type NANOS2, suggesting the existence of other NANOS2-associated factor(s) that determine the specificity of RNA-binding independently of the CCR4-NOT deadenylation complex.