Antibiotic resistance often confers a fitness cost to the resistant cell and thus raises key questions of how resistance is maintained in the absence of antibiotics and, if lost, whether cells are genetically primed for re-evolving resistance. To address these questions, we have examined vancomycin-intermediate Staphylococcus aureus (VISA) strains that arise during vancomycin therapy. VISA strains harbor a broad spectrum of mutations, and they are known to be unstable both in patients and in the laboratory. Here, we show that loss of resistance in VISA strains is correlated with a fitness increase and is attributed to adaptive mutations, leaving the initial VISA-adaptive mutations intact. Importantly, upon a second exposure to vancomycin, such revertants evolve significantly faster to become VISA, and they reach higher resistance levels than vancomycin-naive cells. Further, we find that sub-lethal concentrations of vancomycin stabilize the VISA phenotype, as do the human β-defensin 3 (hBD-3) and the bacteriocin nisin that both, like vancomycin, bind to the peptidoglycan building block, lipid II. Thus, factors binding lipid II may stabilize VISA both in vivo and in vitro, and in case resistance is lost, mutations remain that predispose to resistance development. These findings may explain why VISA infections often are re-occurring and suggest that previous vancomycin adaptation should be considered a risk factor when deciding on antimicrobial chemotherapy.