The mRNA cap structure is bound by either the nuclear (CBC) or the cytoplasmic (eIF4F) cap binding complex. Following mRNA export, CBC must be exchanged for eIF4F in the cytoplasm. It is not known how this exchange occurs or how this RNP remodeling event is integrated with mRNA function. Here we report genetic and biochemical evidence that the yeast translation initiation factor eIF4G associates with CBC, and that eIF4E, the eIF4F component that binds both the cap and eIF4G, antagonizes this interaction. Furthermore, we find that CBC can stimulate translation in extracts containing an eIF4G protein deficient for eIF4E binding. These data suggest that eIF4E binding to the eIF4G-CBC complex on newly exported mRNA displaces CBC, and that the first round of translation on mRNA may occur via a different mechanism than subsequent rounds.