Waves in the spatio-spectral and -temporal coherence of evolving ultra-intense twin beams are predicted: Twin beams with low intensities attain maximal coherence in the beam center until certain threshold intensity is reached. Then the area of maximal coherence moves with increasing intensity from the beam center towards its edges leaving the beam center with low coherence (the first coherence wave). For even larger intensities, a new coherence maximum is gradually built in the beam center with the increasing intensity and, later, it again moves towards the beam edges forming the second coherence wave. Rotationally-symmetric twin beams are analyzed within a three-dimensional model that couples spectral and spatial degrees of freedom. Relation between the twin-beam coherence and its local density of modes during the nonlinear evolution is discussed.