In this work, an electrochemical aptamer-based biosensor was fabricated on a pencil graphite electrode (PGE). The bare PGE was modified with a nanocomposite including reduced graphene oxide (RGO) and Au nanoparticles for sulfadimethoxine (SDM) determination. In order to fabricate the electrode in different stages, cyclic voltammetry and electrochemical impedance spectroscopy were employed. Some factors, such as RGO synthesis/preparation time (90 min), immobilization time of aptamer (80 min), aptamer concentration (12.5 μM), and binding time of SDM (50 min) were optimized to prepare the working electrode surface. Under the optimal experiments, the proposed aptasensor displayed a wide linear range from 1.0 × 10−15 to 1.0 × 10−5 M with a limit of detection (LOD) of 3.7 × 10−16 M towards SDM. Additionally, it has a high reproducibility, good selectivity, and acceptable stability. For meat sample applications, the designed aptasensor was applied to fish, chicken, and beef. The aptasensor demonstrated acceptability recovery rates over the range of 92–103%. This electrochemical biosensor can also be used for accurate monitoring of antibiotics in other food products.