Antibiotic resistance is driven by selection, but the degree to which a bacterial strain’s evolutionary history shapes the mechanism and strength of resistance remains an open question. Here, we reconstruct the genetic and evolutionary mechanisms of carbapenem resistance in a clinical isolate of Klebsiella quasipneumoniae. A combination of short- and long-read sequencing, machine learning, and genetic and enzymatic analyses established that this carbapenem-resistant strain carries no carbapenemase-encoding genes. Genetic reconstruction of the resistance phenotype confirmed that two distinct genetic loci are necessary in order for the strain to acquire carbapenem resistance. Experimental evolution of the carbapenem-resistant strains in growth conditions without the antibiotic revealed that both loci confer a significant cost and are readily lost by de novo mutations resulting in the rapid evolution of a carbapenem-sensitive phenotype. To explain how carbapenem resistance evolves via multiple, low-fitness single-locus intermediates, we hypothesised that one of these loci had previously conferred adaptation to another antibiotic. Fitness assays in a range of drug concentrations show how selection in the antibiotic ceftazidime can select for one gene (blaDHA-1) potentiating the evolution of carbapenem resistance by a single mutation in a second gene (ompK36). These results show how a patient’s treatment history might shape the evolution of antibiotic resistance and could explain the genetic basis of carbapenem-resistance found in many enteric-pathogens.