eIF4E-binding proteins (4E-BPs) regulate translation of mRNAs in eukaryotes. However the extent to which specific mRNA targets are regulated by 4E-BPs remains unknown. We performed translational profiling by microarray analysis of polysome and monosome associated mRNAs in wild-type and mutant cells to identify mRNAs in yeast regulated by the 4E-BPs Caf20p and Eap1p; the first-global comparison of 4E-BP target mRNAs. We find that yeast 4E-BPs modulate the translation of >1000 genes. Most target mRNAs differ between the 4E-BPs revealing mRNA specificity for translational control by each 4E-BP. This is supported by observations that eap1Δ and caf20Δ cells have different nitrogen source utilization defects, implying different mRNA targets. To account for the mRNA specificity shown by each 4E-BP, we found correlations between our data sets and previously determined targets of yeast mRNA-binding proteins. We used affinity chromatography experiments to uncover specific RNA-stabilized complexes formed between Caf20p and Puf4p/Puf5p and between Eap1p and Puf1p/Puf2p. Thus the combined action of each 4E-BP with specific 3'-UTR-binding proteins mediates mRNA-specific translational control in yeast, showing that this form of translational control is more widely employed than previously thought.