Salmonella is one of the most common causes of food-associated disease. An electrochemical biosensor was developed for Salmonella detection using a Salmonella-specific recognition aptamer. The biosensor was based on a glassy carbon electrode modified with graphene oxide and gold nanoparticles. Then, the aptamer ssDNA sequence could be linked to the electrode. Each assembly step was accompanied by changes to the electrochemical parameters. After incubation of the modified electrode with Salmonella, the electrochemical properties between the electrode and the electrolyte changed accordingly. The electrochemical impedance spectrum was measured to quantify the Salmonella. The results revealed that, when more Salmonella were added to the reaction system, the current between the electrode and electrolyte decreased; in other words, the impendence gradually increased. A detection limit as low as 3 cfu/mL was obtained. This novel method is specific and fast, and it has the potential for real sample detection.