Antibiotic resistance is a major threat to public health, undermining our ability to treat infectious disease. Often, isolates bearing resistance mutations suffer a cost of resistance, that is, lower fitness than their susceptible counterparts. Nonetheless, fitness can be ameliorated by compensatory mutations. These mutations restore fitness to normal levels without eliminating resistance. Despite the potential importance of compensation for public health strategies to combat antibiotic resistance, relatively little is known about the molecular mechanisms of compensation. Here, we investigate mechanisms of compensation for quinolone resistance mutations in Escherichia coli. We found substantial costs of resistance for gyrA D87G and marR R94C mutants. Subsequent selection in the absence of antibiotics led to an improvement in fitness, with at least partial retention of resistance. Putative compensatory mutations that arise in a gyrA D87G mutant encode for cell adhesion, while on the marR R94C background occur in genes that function in outer membrane.