How does a star cluster of more than few 10,000 solar masses form? We present the case of the cluster NGC 346 in the Small Magellanic Cloud, still embedded in its natal star-forming region N66, and we propose a scenario for its formation, based on observations of the rich stellar populations in the region. Young massive clusters host a high fraction of early-type stars, indicating an extremely high star formation efficiency. The Milky Way galaxy hosts several young massive clusters that fill the gap between young low-mass open clusters and old massive globular clusters. Only a handful, though, are young enough to study their formation. Moreover, the investigation of their gaseous natal environments suffers from contamination by the Galactic disk. Young massive clusters are very abundant in distant starburst and interacting galaxies, but the distance of their hosting galaxies do not also allow a detailed analysis of their formation. The Magellanic Clouds, on the other hand, host young massive clusters in a wide range of ages with the youngest being still embedded in their giant HII regions. Hubble Space Telescope imaging of such star-forming complexes provide a stellar sampling with a high dynamic range in stellar masses, allowing the detailed study of star formation at scales typical for molecular clouds. Our cluster analysis on the distribution of newly-born stars in N66 shows that star formation in the region proceeds in a clumpy hierarchical fashion, leading to the formation of both a dominant young massive cluster, hosting about half of the observed pre–main-sequence population, and a self-similar dispersed distribution of the remaining stars. We investigate the correlation between stellar surface density (and star formation rate derived from star-counts) and molecular gas surface density (derived from dust column density) in order to unravel the physical conditions that gave birth to NGC 346. A power law fit to the data yields a steep correlation between these two parameters with a considerable scatter. The fraction of stellar over the total (gas plus young stars) mass is found to be systematically higher within the central 15 pc (where the young massive cluster is located) than outside, which suggests variations in the star formation efficiency within the same star-forming complex. This trend possibly reflects a change of star formation efficiency in N66 between clustered and non-clustered star formation. Our findings suggest that the formation of NGC 346 is the combined result of star formation regulated by turbulence and of early dynamical evolution induced by the gravitational potential of the dense interstellar medium.