The yeast pheromone pathway consists of a canonical heterotrimeric G protein and MAP kinase cascade. To identify additional signaling components, we systematically evaluated 870 essential genes using a library of repressible-promoter strains. Quantitative transcription-reporter and MAPK activity assays were used to identify strains that exhibit altered pheromone sensitivity. Of the 92 newly identified essential genes required for proper G protein signaling, those involved with protein degradation were most highly represented. Included in this group are members of the Skp, Cullin, F box (SCF) ubiquitin ligase complex. Further genetic and biochemical analysis reveals that SCF Cdc4 acts together with the Cdc34 ubiquitin-conjugating enzyme at the level of the G protein; promotes degradation of the G protein α subunit, Gpa1, in vivo; and catalyzes Gpa1 ubiquitination in vitro. These insights to the G protein signaling network reveal the essential genome as an untapped resource for identifying new components and regulators of signal transduction pathways.