Using first-principles numerical simulations, we find a new spatially inhomogeneous phase in a rotating gluon plasma. This mixed phase simultaneously contains regions of both confining and deconfining states in thermal equilibrium, separated by a spatial transition. The position of the boundary between the two phases is determined by the local critical temperature. We calculate the critical temperature of the local transition as a function of angular velocity and radius for a full (imaginary) rotating system and within a local thermalization approximation, and find an excellent agreement between these approaches. An analytic continuation of the results to the domain of real angular frequencies indicates that the confinement phase localizes at the periphery of the rotating system and the deconfinement phase appears closer to the rotation axis. We argue that the anisotropy of the gluon action in the curved co-rotating background can quantitatively explain the remarkable property that the spatial structure of this inhomogeneous phase disobeys the picture based on a straightforward implementation of the Tolman-Ehrenfest law. We also perform the first lattice simulation of rotating $N_f=2$ QCD which confirms that a similar picture is expected for theory with dynamical quarks.