Cell shape is linked to cell function. The significance of cell morphodynamics, namely the temporal fluctuation of cell shape, is much less understood. Here we study the morphodynamics of MDA-MB-231 cells in type I collagen extracellular matrix (ECM). We systematically vary ECM physical properties by tuning collagen concentrations, alignment, and gelation temperatures. We find that morphodynamics of 3D migrating cells are externally controlled by ECM mechanics and internally modulated by Rho/ROCK-signaling. We employ machine learning to classify cell shape into four different morphological phenotypes, each corresponding to a distinct migration mode. As a result, we map cell morphodynamics at mesoscale into the temporal evolution of morphological phenotypes. We characterize the mesoscale dynamics including occurrence probability, dwell time and transition matrix at varying ECM conditions, which demonstrate the complex phenotype landscape and optimal pathways for phenotype transitions. In light of the mesoscale dynamics, we show that 3D cancer cell motility is a hidden Markov process whereby the step size distributions of cell migration are coupled with simultaneous cell morphodynamics. Morphological phenotype transitions also facilitate cancer cells to navigate non-uniform ECM such as traversing the interface between matrices of two distinct microstructures. In conclusion, we demonstrate that 3D migrating cancer cells exhibit rich morphodynamics that is controlled by ECM mechanics, Rho/ROCK-signaling, and regulate cell motility. Our results pave the way to the functional understanding and mechanical programming of cell morphodynamics as a route to predict and control 3D cell motility.