Preserving the three dimensions (3D) fibrous structure of paper-based working electrodes during the addition of conductivity to the filter paper sheets could be challenging. Protecting the paper electrode porosity could easily lead a higher surface area and therefore, higher sensitivity for electrochemical analyte sensing. Herein, various shapes of Au dendritic nanostructures have grown on the paper fibers by an electrodeposition process from HAuCl4 precursor and in the short time of 4.0 min. The effect of different experimental parameters including deposition potential, concentration of HAuCl4 solution and paper thickness on the electrodeposition results were investigated and discussed. The electrochemical behavior of the different deposited Au nanostructures was compared. Finally, the paper-based electrode modified by Au dendrites showed an efficient catalytic role for the non-enzymatic oxidation of glucose. The parameters effecting the performance of the sensor were investigated and optimized. Finally, it was used as sensor for measurement of glucose. The obtained linear calibration curve for the designed biosensor showed a wide concentration range of 10.0 μM to 15.0 mM with the limit of detection of 0.6 μM.