The evolution of resistance to a single antibiotic is frequently accompanied by increased resistance to multiple other antimicrobial agents. In sharp contrast, very little is known about the frequency and mechanisms underlying collateral sensitivity. In this case, genetic adaptation under antibiotic stress yields enhanced sensitivity to other antibiotics. Using large-scale laboratory evolutionary experiments with Escherichia coli, we demonstrate that collateral sensitivity occurs frequently during the evolution of antibiotic resistance. Specifically, populations adapted to aminoglycosides have an especially low fitness in the presence of several other antibiotics. Whole-genome sequencing of laboratory-evolved strains revealed multiple mechanisms underlying aminoglycoside resistance, including a reduction in the proton-motive force (PMF) across the inner membrane. We propose that as a side effect, these mutations diminish the activity of PMF-dependent major efflux pumps (including the AcrAB transporter), leading to hypersensitivity to several other antibiotics. More generally, our work offers an insight into the mechanisms that drive the evolution of negative trade-offs under antibiotic selection.