Battling a widespread pandemic is an arms race between our mitigation efforts, e.g., social distancing or vaccination, and the pathogen's evolving persistence. This is being observed firsthand during the current COVID-19 crisis, as novel mutations are constantly challenging our global vaccination race. To address this, we introduce here a general framework for epidemic spreading under pathogen evolution, which shows that mutations can fundamentally alter the projection of the spread. Specifically, we detect a new pandemic phase - the mutated phase - in which, despite the fact that the pathogen is initially non-pandemic (R0 < 1), it may still spread due to the emergence of a critical mutation. The boundaries of this phase portray a balance between the epidemic and the evolutionary time-scales. If the mutation rate is too low, the pathogen prevalence decays prior to the appearance of a critical mutation. On the other hand, if mutations are too rapid, the pathogen evolution becomes volatile and, once again, it fails to spread. Between these two extremes, however, a broad range of conditions exists in which an initially sub-pandemic pathogen will eventually gain prevalence. This is especially relevant during vaccination, which creates, as it progresses, increasing selection pressure towards vaccine-resistance. To overcome this, we show that vaccination campaigns must be accompanied by fierce mitigation efforts, to suppress the potential rise of a resistant mutant strain.