We studied the electrochemical properties of gold nanoparticles (GNPs) and their complexes with proteins using square-wave voltammetry. Effect of the nanoparticle size and detection procedure was explored upon the oxidation of GNPs on a glassy carbon electrode (GCE). For pre-characterized GNPs of 13, 35 and 78 nm diameter, the oxidation peak potential was +0.98, +1.03 and +1.06 V vs. Ag/AgCl, respectively. The conjugation of GNPs with four different proteins was verified by UV-Vis spectroscopy and atomic force microscopy indicated the formation of protein shells around GNPs. This process hampered the oxidation of GNPs on bare GCE causing pronounced decrease in the current response by an average factor of 72. GCE modification with carbon nanotubes weakly influenced the sensitivity of GNP detection but resulted in a 14.5-fold signal increase averaged for all GNP-protein complexes. The acidic dissolution and electrodeposition of GNPs or their complexes adsorbed on GCE allowed superior signal amplification directly proportional to nanoparticle size. The results are useful for the optimization of voltammetric analysis of GNP-protein complexes and can be extended to the characterization of other metal nanostructures and their complexes with biological components.