The movement of many transcription factors, kinases and replication factors between the nucleus and cytoplasm is important in regulating their activity. In some cases, phosphorylation of a protein regulates its entry into the nucleus; in others, it causes the protein to be exported to the cytoplasm. The mechanism by which phosphorylation promotes protein export from the nucleus is poorly understood. Here we investigate how the export of the yeast transcription factor Pho4 is regulated in response to changes in phosphate availability. We show that phosphorylation of Pho4 by a nuclear complex of a cyclin with a cyclin-dependent kinase, Pho80-Pho85, triggers its export from the nucleus. We also find that the shuttling receptor used by Pho4 for nuclear export is the importin-beta-family member Msn5, which is required for nuclear export of Pho4 in vivo and binds only to phosphorylated Pho4 in the presence of the GTP-bound form of yeast Ran in vitro. Our results reveal a simple mechanism by which phosphorylation can control the nuclear export of a protein.