The ARF tumor suppressor protein stabilizes p53 by antagonizing its negative regulator, Mdm2 (Hdm2 in humans). Both mouse p19(ARF) and human p14(ARF) bind to the central region of Mdm2 (residues 210 to 304), a segment that does not overlap with its N-terminal p53-binding domain, nuclear import or export signals, or C-terminal RING domain required for Mdm2 E3 ubiquitin ligase activity. The N-terminal 37 amino acids of mouse p19(ARF) are necessary and sufficient for binding to Mdm2, localization of Mdm2 to nucleoli, and p53-dependent cell cycle arrest. Although a nucleolar localization signal (NrLS) maps within a different segment (residues 82 to 101) of the human p14(ARF) protein, binding to Mdm2 and nucleolar import of ARF-Mdm2 complexes are both required for cell cycle arrest induced by either the mouse or human ARF proteins. Because many codons of mouse ARF mRNA are not recognized by the most abundant bacterial tRNAs, we synthesized ARF minigenes containing preferred bacterial codons. Using bacterially produced ARF polypeptides and chemically synthesized peptides conjugated to Sepharose, residues 1 to 14 and 26 to 37 of mouse p19(ARF) were found to interact independently and cooperatively with Mdm2, while residues 15 to 25 were dispensable for binding. Paradoxically, residues 26 to 37 of mouse p19(ARF) are also essential for ARF nucleolar localization in the absence of Mdm2. However, the mobilization of the p19(ARF)-Mdm2 complex into nucleoli also requires a cryptic NrLS within the Mdm2 C-terminal RING domain. The Mdm2 NrLS is unmasked upon ARF binding, and its deletion prevents import of the ARF-Mdm2 complex into nucleoli. Collectively, the results suggest that ARF binding to Mdm2 induces a conformational change that facilitates nucleolar import of the ARF-Mdm2 complex and p53-dependent cell cycle arrest. Hence, the ARF-Mdm2 interaction can be viewed as bidirectional, with each protein being capable of regulating the subnuclear localization of the other.