Noise and spatial degrees of freedom characterize most ecosystems. Some aspects of their influence on the coevolution of populations with cyclic interspecies competition have been demonstrated in recent experiments e.g., B. Kerr , Nature (London) 418, 171 (2002)]. To reach a better theoretical understanding of these phenomena, we consider a paradigmatic spatial model where three species exhibit cyclic dominance. Using an individual-based description, as well as stochastic partial differential and deterministic reaction-diffusion equations, we account for stochastic fluctuations and spatial diffusion at different levels and show how fascinating patterns of entangled spirals emerge. We rationalize our analysis by computing the spatiotemporal correlation functions and provide analytical expressions for the front velocity and the wavelength of the propagating spiral waves.