Spatial beam self-cleaning, a manifestation of the Kerr effect in graded-index multimode fibers, involves a nonlinear transfer of power among modes, which leads to robust bell-shaped output beams. The resulting mode power distribution can be described by statistical mechanics arguments. Although the spatial coherence of the output beam was experimentally demonstrated, there is no direct study of modal phase evolutions. Based on a holographic mode decomposition method, we reveal that nonlinear spatial phase-locking occurs between the fundamental and its neighboring low-order modes, in agreement with theoretical predictions. As such, our results dispel the current belief that the spatial beam self-cleaning effect is the mere result of a wave thermalization process.