Evolutionary dynamics is determined by mutation and selection within a population, co-evolutionary dynamics between populations, and stochastic noise. Inspired by the co-evolution of mutating virus and adaptive immune system, we analyze a unified model that includes all three of these forces. Simulation results and theoretical analysis show how these forces interact in novel and unanticipated ways. For instance, the classical error thresholds for virus and immune system (a maximal mutation rate to avoid delocalization in genotype space) become interdependent due to co-evolutionary interactions. Further, oscillatory dynamics, which can be of a regular or intermittent type, is only induced by stochastic number fluctuations. By means of advanced techniques for stochastic analysis in high-dimensional nonlinear systems, we show how and when periodic cycling turns into intermittent dynamics. Our model unifies three main forces of co-evolutionary dynamics that have so far been mostly treated separately, and our methods and conclusions should be relevant in many other contexts such as game theory or epidemics.