Populations often encounter environmental changes that remove selection for the maintenance of certain phenotypic traits. The resulting decay of these traits under relaxed selection reduces an organism’s fitness in its prior environment. However, how these traits subsequently evolve upon restoration of selection is not well-understood. We addressed this question using Escherichia coli strains from the long-term evolution experiment (LTEE) that have been independently evolving for multiple decades in the absence of antibiotics. We confirmed that these derived strains have typically become more sensitive to various antibiotics during this time. We then asked how readily the bacteria could overcome these losses of intrinsic resistance through subsequent evolution when challenged with these same drugs. In our study, we focused on the role that genetic background plays in this process, with attention to the tension between evolutionary repeatability and contingency. We found that idiosyncratic responses in evolvability dominated over trends of diminishing returns, such that the potential to evolve increased resistance was hampered on some derived genetic backgrounds. We further subjected a time-series of clones from one LTEE population to tetracycline and showed that evolutionary constraint occurred early in its history. Taken together, our results indicate that the evolution and diversification of a single species in an antibiotic-free environment can render resistance evolution unpredictable, even for closely related strains. Current work is now centered on characterizing the genomic changes underlying resistance to address whether the same genes are the focus of selection when strains have evolved for decades in the absence of antibiotics.