Cyclin-dependent kinases (CDKs) control the eukaryotic cell cycle, and a single CDK, Cdc28 (also known as Cdk1), is necessary and sufficient for cell cycle regulation in the budding yeast Saccharomyces cerevisiae. Cdc28 regulates cell cycle-dependent processes such as transcription, DNA replication and repair, and chromosome segregation. To gain further insight into the functions of Cdc28, we performed a high-throughput chemical-genetic array (CGA) screen aimed at unraveling the genetic network of CDC28. We identified 107 genes that strongly genetically interact with CDC28. Although these genes serve multiple cellular functions, genes involved in cell cycle regulation, transcription, and chromosome metabolism were overrepresented. DOA1, which is involved in maintaining free ubiquitin levels, as well as the RAD6-BRE1 pathway, which is involved in transcription, displayed particularly strong genetic interactions with CDC28. We discovered that DOA1 is important for cell cycle entry by supplying ubiquitin. Furthermore, we found that the RAD6-BRE1 pathway functions downstream of DOA1/ubiquitin but upstream of CDC28, by promoting transcription of cyclins. These results link cellular ubiquitin levels and the Rad6-Bre1 pathway to cell cycle progression.