The nucleation and dynamics of gas bubbles are of fundamental interest. Herein, we use Pt nanodisk electrodes (apparent radii from 4 to 80 nm) to investigate the nucleation of individual O2 nanobubbles generated by electrooxidation of hydrogen peroxide (H2O2). A single bubble reproducibly nucleates when the dissolved O2 concentration reaches ~0.17 M at the Pt electrode surface. This nucleation concentration is ~130 times higher than the equilibrium saturation concentration of O2 and is independent of electrode size. Moreover, in acidic H2O2 solutions (1 M HClO4), in addition to producing an O2 nanobubble through H2O2 oxidation at positive potentials, individual H2 nanobubbles can also be generated at negative potentials. Alternating generation of single O2 and H2 bubbles within the same experiment allows direct comparison of the critical concentrations for nucleation of each nanobubble without knowing the precise size/geometry of the electrode, or the exact viscosity/temperature of the solution.