Folding-based electrochemical sensors utilizing structure-switching aptamers are specific, selective, sensitive, and widely applicable to the detection of a variety of target analytes. The specificity is achieved by the binding properties of an electrode-bound RNA or DNA aptamer biorecognition element. Signaling in this class of sensors arises from changes in electron transfer efficiency upon target-induced changes in the conformation/flexibility of the aptamer probe. These changes can be readily monitored electrochemically. Because of this signaling mechanism, there are several approaches to maximizing the analytical attributes (i.e., sensitivity, limit of detection, and observed binding affinity) of the aptamer sensor. Here, we present a systematic study of several approaches, including electrochemical interrogation parameters and biomolecular engineering of the aptamer sequence, to develop a sensor for the detection of aminoglycoside antibiotics. Specifically, through a combination of optimizing the electrochemical signal and engineering the parent 26-nucleotide RNA aptamer sequence to undergo larger conformation changes, we develop several improved sensors. These sensors exhibit binding affinities ranging from 220 nM to 42 μM, as much as a 100-fold improved limit of detection in comparison to previously reported sensors, and a variety of linear ranges including the therapeutic window for tobramycin. These data demonstrate that rational engineering of the aptamer structure to create large conformation changes upon target binding leads to improved sensor performance. We believe that the sensor design guidelines outlined here represent a general strategy for developing new aptamer folding-based electrochemical sensors.