Robust composite nanofibers (NFs) are prerequisite for highly efficient electrochemical sensors. We report the electrochemical application of gold nanoparticle (Au NP)-composite Nafion NFs using a facile electrospinning technique. Owing to the uniform distribution and large surface area of the Au NPs in the NFs, the Au NP-composite electrodes gave rise to greatly improved electrochemical properties, compared to AuNP-free composite electrodes. When they were employed as reservoirs for immobilizing horseradish peroxidase (HRP), reliable and sensitive electrochemical detection by the enzyme reaction was achieved. The detection sensitivity for H2O2 was determined to be as low as 38 nM, which was one order higher than that of previous electrochemical sensors. In addition, there was no change in the enzyme stability over three weeks. In this regard, the developed NP/NF-based electrochemical sensors are anticipated to be very suitable for monitoring other enzyme reactions with high sensitivity and stability.