The eukaryotic cell cycle is a process controlled by protein assemblies, of which the key subunits are serine-threonine cyclin-dependent kinases (CDKs). Timely association and dissociation of these assemblies ensure that the cell division program is executed correctly. The challenge to unravel the rules of the plant cell cycle results from the multiplicity of the process-regulating genes that emerged through genome duplications during the evolution of flowering plants. Despite the increasing knowledge on the plant cell cycle control, little is known about the composition of the different CDK-Cyclin complexes and their spatiotemporal occurrence. The binary interactions of the previously annotated 58 Arabidopsis thaliana core cell cycle proteins were tested in two high-throughput protein-protein interaction (PPI) assays: the bimolecular fluorescence complementation (BiFC) and the yeast two-hybrid. The resulting PPI network was integrated with available cycle phase-dependent gene expression data and subcellular localization information, revealing distinct cell cycle clusters acting at different cell division stages. Additionally, the BiFC assay revealed that three D-type cyclins, CYCD4;1, CYCD4;2 and CYCD5;1, form active kinase complexes with CDKA;1 and CDKB1;1 in vivo because they induce cell divisions in differentiated tobacco (Nicotiana benthamiana) epidermal cells. We demonstrate that these complexes promote cell proliferation in Arabidopsis and we discuss their putative mode of action in plant development.