Ochratoxin A (OTA) is a mycotoxin widely found in foodstuffs such as cereal grains. It greatly threatens human health owing to its strong toxicity and high stability. Aptasensors have emerged as promising tools for the analysis of small molecule contaminants. Nucleic-acid-based signal amplification enables detectable signals to be obtained from aptasensors. However, this strategy often requires the use of complex primers or multiple enzymes, entailing problems such as complex system instability. Herein, we propose a fluorescent aptasensor for the ultrasensitive detection of OTA in cereal products, with signal amplification through RecJ exonuclease-assisted target recycling. The aptamer/fluorescein-labeled complementary DNA (cDNA-FAM) duplex was effectively used as the target-recognition unit as well as the potential substrate for RecJ exonuclease cleavage. When the target invaded the aptamer-cDNA-FAM duplex to release cDNA-FAM, RecJ exonuclease could cleave the aptamer bonded with the target and release the target. Thus, the target-triggered cleavage cycling would continuously generate cDNA-FAM as a signaling group, specifically amplifying the response signal. The proposed exonuclease-assisted fluorescent aptasensor exhibited a good linear relationship with OTA concentration in the range from 1 pg/mL to 10 ng/mL with an ultralow limit of detection (6.2 ng/kg of cereal). The analytical method showed that recoveries of the cereal samples ranged from 83.7 to 109.3% with a repeatability relative standard deviation below 8%. Importantly, the proposed strategy is expected to become a common detection model because it can be adapted for other targets by replacing the aptamer. Thus, this model can guide the development of facile approaches for point-of-care testing applications.