We show that the noncrystalline-to-crystalline transition of supported Pt nanoparticles (NPs) in the subnanometer to nanometer size range is statistical in nature, and strongly affected by particle size, support, and adsorbates (here we use H2). Unlike in the bulk, a noncrystalline phase exists and is stable in small NPs, reflecting a general mesoscopic feature. Observations of >3000 particles by high-resolution transmission electron microscopy show a noncrystalline-to-crystalline transition zone that is nonabrupt; there is a size regime where disordered and ordered NPs coexist. The NP size at which this transition occurs is strongly dependent on both the adsorbate and the support, and this effect is general for late 5d transition metals. All results are reconciled via a statistical description of particle-support-adsorbate interactions.