Catalytically driven electrochemical hydrogen evolution reaction (HER) of monolayered molybdenum disulfide (MoS2) is usually highly suppressed by the scarcity of edges and low electrical conductivity. Here, we show how the catalytic performance of MoS2 monolayers can be improved dramatically by catalyst size reduction and surface sulfur (S) depletion. Monolayered MoS2 nanocrystals (NCs) (2-25 nm) produced via exfoliating and disintegrating their bulk counterparts showed improved catalysis rates over monolayer sheets because of their increased edge ratios and metallicity. Subsequent S depletion of these NCs further improved the metallicity and made Mo atoms on the basal plane become catalytically active. As a result, the S-depleted NCs with low mass (���1.2 ��g) showed super high catalytic performance on HER with a low Tafel slope of ���29 mV/decade, overpotentials of 60-75 mV, and high current densities jx (where x is in mV) of j150 = 9.64 mA��cm-2 and j200 = 52.13 mA��cm-2. We have found that higher production rates of H2 could not be achieved by adding more NC layers since HER only happens on the topmost surface and the charge mobility decreases dramatically. These difficulties can be largely alleviated by creating a hybrid structure of NCs immobilized onto three-dimensional graphene to provide a very high surface exposure of the catalyst for electrochemical HER, resulting in very high current densities of j150 = 49.5 mA��cm-2 and j200 = 232 mA��cm-2 with ���14.3 ��g of NCs. Our experimental and theoretical studies show how careful design and modification of nanoscale materials/structures can result in highly efficient catalysis. There may be considerable opportunities in the broader family of transition metal dichalcogenides beyond just MoS2 to develop highly efficient atomically thin catalysts. These could offer cheap and effective replacement of precious metal catalysts in clean energy production.