An electrochemical aptasensor is described for the detection of prostate specific antigen (PSA). The aptasensor is based on the use of hemin-functionalized graphene-conjugated palladium nanoparticles (H-Gr/PdNPs) deposited on a glassy carbon electrode. The nanocomposites integrate the high electrical conductivity of graphene with the easily functionalized surface chemistry of PdNPs and their excellent catalytic property. The hemin placed on graphene acts as both a protective agent and an in-situ redox probe. The PdNPs provide numerous binding sites for the immobilization of DNA-biotin via coordinative binding between Pd and amino groups. A sensitive and specific PSA assay was attained by immobilizing the PSA aptamer via biotin-streptavidin interaction. The resulting aptasensor has a linear response that covers the PSA concentration range from 0.025 to 205 ng·mL, with a 8 pg·mL lower detection limit (at -0.362 V, scan rate: 0.1 mV·s, S/N = 3). The method was applied to the quantitation of PSA in spiked serum samples, giving recoveries ranging from 95.0 to 100.3%. Graphical abstract A signal amplified and approving electrochemical aptasensor was constructed for the determination of prostate specific antigen (PSA) based on the use of hemin-functionalized graphene conjugated to palladium nanoparticles (H-Gr/PdNPs). The sensor has a wide linear range, a relatively low detection limit, satisfying stability and high specificity.