Far1 is a bifunctional protein that is required to arrest the cell cycle and establish cell polarity during yeast mating. Here we show that SCF(Cdc4) ubiquitylates Far1 in the nucleus, which in turn targets the multi-ubiquitylated protein to 26S proteasomes most likely located at the nuclear envelope. In response to mating pheromones, a fraction of Far1 was stabilized after its export into the cytoplasm by Ste21/Msn5. Preventing nuclear export destabilized Far1, while conversely cytoplasmic Far1 was stabilized, although the protein was efficiently phosphorylated in a Cdc28-Cln-dependent manner. The core SCF subunits Cdc53, Hrt1 and Skp1 were distributed in the nucleus and the cytoplasm, whereas the F-box protein Cdc4 was exclusively nuclear. A cytoplasmic form of Cdc4 was unable to complement the growth defect of cdc4-1 cells, but it was sufficient to degrade Far1 in the cytoplasm. Our results illustrate the importance of subcellular localization of F-box proteins, and provide an example of how an extracellular signal regulates protein stability at the level of substrate localization.