We propose a novel Kretschmann-type surface plasmon resonance (SPR) sensor chip having a surface covered with electrodeposited gold nanostructures to enhance the sensitivity of SPR biosensing. The nanostructure is three-dimensional and has a larger surface area than a conventional flat surface chip, which increases the amount of protein binding and also induces a large change in the effective dielectric constant of the sensing area. The gold nanostructures were formed by electrodeposition under galvanostatic conditions, so their size could be controlled by manipulating the deposition time and current. The sensing characteristics, including the concentration dependence and noise level, indicated that the performance of the resulting chip (called a Au-black chip) was equivalent to that of a conventional sensor chip. We also determined the optimal electrodeposition conditions to obtain a sharp SPR curve for protein detection assay; the optimal thickness of the gold layer was 50-60 nm. Enhanced protein sensing was demonstrated by using a binding assay of anti-BSA antibody and BSA molecules. The protein binding signal was several times higher than that of the conventional assay. The insights into electrodeposition for SPR sensing presented here will enable improved sensitivity for detecting low-concentration and small proteins.