We are reporting a new type of synchronization, termed dancing synchronization, between two spin-torque nano-oscillators (STNOs) coupled through spin waves. Different from the known synchronizations in which two STNOs are locked with various fixed relative phases, in this new synchronized state two STNOs have the same frequency, but their relative phase varies periodically within the common period, resulting in a dynamic waving pattern. The amplitude of the oscillating relative phase depends on the coupling strength of two STNOs, as well as the driven currents. The dancing synchronization turns out to be universal, and can exist in two nonlinear Van der Pol oscillators coupled both reactively and dissipativly. Our findings open doors for new functional STNO-based devices.