When yeast cells enter into quiescence in response to nutrient limitation, the adenine deaminase Aah1p is specifically degraded via a process requiring the F-box protein Saf1p and components of the Skp1-Cullin-F-box complex. In this paper, we show that Saf1p interacts with both Aah1p and Skp1p. Interaction with Skp1p, but not with Aah1p, requires the F-box domain of Saf1p. Based on deletion and point mutations, we further demonstrate that the F-box domain of Saf1p is critical for degradation of Aah1p. We also establish that overexpression of Saf1p in proliferating cells is sufficient to trigger the degradation of Aah1p. Using this property and a two-dimensional protein gel approach, we found that Saf1p has a small number of direct targets. Finally, we isolated and characterized several point mutations in Aah1p, which increase its stability during quiescence. The majority of the mutated residues are located in two distinct exposed regions in the Aah1p three-dimensional model structure. Two hybrid experiments strongly suggest that these domains are directly involved in interaction with Saf1p. Importantly, we obtained a mutation in Aah1p that does not affect the protein interaction with Saf1p but abolishes Aah1p degradation. Because this mutated residue is an exposed lysine in the Aah1p three-dimensional model, we propose that it is likely to be a major ubiquitylation site. All together, our data strongly argue for Saf1p being a bona fide Skp1-Cullin-F-box subunit.