Glucose-dependent regulation of carbon metabolism is a subject of intensive studies. We have previously shown that the switch from gluconeogenesis to glycolysis is associated with ubiquitin-proteasome linked elimination of the key enzyme fructose-1,6-bisphosphatase. Seven glucose induced degradation deficient (Gid)-proteins found previously in a genomic screen were shown to form a complex that binds FBPase. One of the subunits, Gid2/Rmd5, contains a degenerated RING finger domain. In an in vitro assay, heterologous expression of GST-Gid2 leads to polyubiquitination of proteins. In addition, we show that a mutation in the degenerated RING domain of Gid2/Rmd5 abolishes fructose-1,6-bisphosphatase polyubiquitination and elimination in vivo. Six Gid proteins are present in gluconeogenic cells. A seventh protein, Gid4/Vid24, occurs upon glucose addition to gluconeogenic cells and is afterwards eliminated. Forcing abnormal expression of Gid4/Vid24 in gluconeogenic cells leads to fructose-1,6-bisphosphatase degradation. This suggests that Gid4/Vid24 initiates fructose-1,6-bisphosphatase polyubiquitination by the Gid complex and its subsequent elimination by the proteasome. We also show that an additional gluconeogenic enzyme, phosphoenolpyruvate carboxykinase, is subject to Gid complex-dependent degradation. Our study uncovers a new type of ubiquitin ligase complex composed of novel subunits involved in carbohydrate metabolism and identifies Gid4/Vid24 as a major regulator of this E3.