A novel electrochemical aptasensor is described for rapid and ultrasensitive detection of ochratoxin A (OTA) based on signal enhancement with rolling circle amplification (RCA). The primer for RCA was designed to compose of a two-part sequence, one part of the aptamer sequence directed against OTA while the other part was complementary to the capture probe on the electrode surface. In the presence of target OTA, the primer, originally hybridized with the RCA padlock, is replaced to combine with OTA. This induces the inhibition of RCA and decreases the OTA sensing signal obtained with the electrochemical aptasensor. Under the optimized conditions, ultrasensitive detection of OTA was achieved with a limit of detection (LOD) of 0.065 ppt (pg/mL), which is much lower than previously reported. The electrochemical aptasensor was also successfully applied to the determination of OTA in wine samples. This ultrasensitive electrochemical aptasensor is of great practical importance in food safety and could be widely extended to the detection of other toxins by replacing the sequence of the recognition aptamer.