We started (sub-)millimeter continuum and line studies of entire molecular cloud complexes located at intermediate distances from the Sun (1–3 kpc). Such an unbiased approach allows to identify and characterize the earliest phases of high-mass stars overlooked by IRAS or MSX. Our complete MAMBO-2 surveys of the Cygnus X and NGC 7538 complexes reveal a large population of ${\sim} 0.1$ pc-size massive young stellar objects (MYSOs) harboring high-mass infrared-quiet protostars. The determination of the nature of all the new millimeter sources is still in progress but we have already collected evidence that the infrared-quiet (or class 0-like) protostellar phase might last as long as the better-known infrared-bright protostellar phase. Besides, our complete census of MYSOs fails to discover the high-mass analogues of pre-stellar dense cores. We propose that the observed lower-density pre-stellar clumps (${>} 1$ pc) rapidly concentrate and collapse as also found in the kinematical studies of other prominent clumps. Indeed, CS and HCO$^+$ mappings in W43 and Cygnus X suggest global supersonic contraction with inward velocities of several km s−1 on parsec scales. Our work and similar studies of entire star-forming complexes will thus definitively contribute to a better knowledge of the earliest phases of high-mass star formation.