The programmed formation of specific tissues from embryonic stem cells is a major goal of regenerative medicine. To identify points of intervention in cardiac tissue formation, we performed an siRNA screen in murine embryonic stem cells to identify ubiquitin system genes that repress cardiovascular tissue formation. Our screen uncovered an F-box protein, Fbxl16, as a repressor of one of the earliest steps in the cardiogenic lineage: FLK1+ progenitor formation. Whereas F-box proteins typically form SCF ubiquitin ligases, shotgun mass spectrometry revealed that FBXL16 instead binds protein phosphatase 2A (PP2A) containing a B55 specificity subunit (PP2A^(B55)). Phosphoproteomic analyses indicate that FBXL16 negatively regulates phosphorylation of the established PP2AB55 substrate, vimentin. We suggest that FBXL16 negatively regulates the activity of B55α-PP2A to modulate the genesis of FLK1+ progenitor cells.