Electrochemical measurements of the nucleation rate of individual H-2 bubbles at the surface of Pt nanoelectrodes (radius = 7-41 nm) are used to determine the critical size and geometry of H-2 nuclei leading to stable bubbles. Precise knowledge of the H-2 concentration at the electrode surface, C-H2(surf) is obtained by controlled current reduction of H+ in a H2SO4 solution. Induction times of single-bubble nucleation events are measured by stepping the current, to control C-H2(surf), while monitoring the voltage. We find that gas nucleation follows a first-order rate process; a bubble spontaneously nucleates after a stochastic time delay, as indicated by a sudden voltage spike that results from impeded transport of H+ to the electrode. Hundreds of individual induction times, at different applied currents and using different Pt nanoelectrodes, are used to characterize the kinetics of phase nucleation. The rate of bubble nucleation increases by four orders of magnitude (0.3-2000 s(-1)) over a very small relative change in C-H2(surf) (0.21-0.26 M, corresponding to a similar to 0.025 V increase in driving force). Classical nucleation theory yields thermodynamic radii of curvature for critical nuclei of 4.4 to 5.3 nm, corresponding to internal pressures of 330 to 270 atm, and activation energies for nuclei formation of 14 to 26 kT, respectively. The dependence of nucleation rate on H-2 concentration indicates that nucleation occurs by a heterogeneous mechanism, where the nuclei have a contact angle of similar to 150 degrees with the electrode surface and contain between 35 and 55 H-2 molecules.