We report a novel non-enzymatic nanocatalyst based approach to construct an electrochemical aptasensor involving the synergistic contribution of a nanoceria (nCe) tag and graphene oxide (GO). The aptamer was immobilized on the surface of a GO modified electrode. The target analyte was captured by the immobilized aptamer via a specific competitive mechanism between the free and the nCe labeled target. The electrochemical signal was generated by monitoring the electro-oxidation of a generic redox species upon reaction with the nCe tag. The signal was further amplified by the GO layer used as an electrode material to immobilize the aptamer and to increase the electron transfer at the electrode surface, further enhancing sensitivity of the assay. This strategy provides a universal platform for sensitive and specific detection of a wide spectrum of aptamer targets. Application of this new design for the electrochemical detection of Ochratoxin A (OTA) is demonstrated. Under optimal conditions, the aptasensor exhibited a linear response to OTA in the range 0.15-180 nM with a detection limit of 0.1 nM. The method has been successfully used for the detection of OTA in cereal samples. This design may offer a new methodology for sensitive and specific detection of a wide spectrum of analytes for medical, environmental and electronic applications.