Cks (cyclin-dependent kinase subunit) proteins interact with cyclin-dependent kinases (Cdks) with high affinity. Mammalian Cks1 and Cks2 bind Cdk1 and Cdk2 and partake in the control of cell cycle progression. We identified Cks-interacting proteins by affinity purification followed by mass spectrometry in the human lymphocytic cell line, Ramos. Apart from known interactors, such as Cdks, we identified a novel Cdk-dependent interaction between Cks proteins and the mitochondrial single-stranded DNA-binding protein (mtSSB). mtSSB binds both Cks1 and Cks2 and undergoes Cdk-dependent phosphorylation. mtSSB is known to participate in replication of mitochodondrial DNA. We demonstrated that mitochondrial morphology and DNA integrity were compromised in cells depleted of both Cks proteins or have inhibited Cdk activity. These features are consistent with the hypothesis of Cks-dependent regulation of mtSSB function and support a direct role in cell cycle proteins in controlling mitochondrial DNA replication.