The circadian clock and the cell cycle are two biological oscillatory processes that coexist within individual cells. These two oscillators were found to interact, which can lead to their synchronization. Here, we develop a method to identify a low-dimensional stochastic model of the coupled system directly from time-lapse imaging in single cells. In particular, we infer the coupling and nonlinear dynamics of the two oscillators from thousands of mouse and human single-cell fluorescence microscopy traces. This coupling predicts multiple phase-locked states showing different degrees of robustness against molecular fluctuations inherent to cellular-scale biological oscillators. For the 1:1 state, the predicted phase-shifts following period perturbations were validated experimentally. Moreover, the phase-locked states are temperature-independent and evolutionarily conserved from mouse to human, hinting at a common underlying dynamical mechanism. Finally, we detect a signature of the coupled dynamics in a physiological context, explaining why tissues with different proliferation states exhibited shifted circadian clock phases.