How small can superconductors be? For isolated nanoparticles subject to quantum size effects, P.W. Anderson in 1959 conjectured that superconductivity could only exist when the electronic level spacing δ is smaller than the superconducting gap energy Δ. Here we report a scanning tunnelling spectroscopy study of superconducting lead (Pb) nanocrystals grown on the (110) surface of InAs. We find that for nanocrystals of lateral size smaller than the Fermi wavelength of the 2D electron gas at the surface of InAs, the electronic transmission of the interface is weak; this leads to Coulomb blockade and enables the extraction of electron addition energy of the nanocrystals. For large nanocrystals, the addition energy displays superconducting parity effect, a direct consequence of Cooper pairing. Studying this parity effect as a function of nanocrystal volume, we find the suppression of Cooper pairing when the mean electronic level spacing overcomes the superconducting gap energy, thus demonstrating unambiguously the validity of the Anderson criterion.