In this review I first describe the nature of the three kinds of High-Mass X-ray Binaries (HMXBs), accreting through: (i) Be circumstellar disc, (ii) supergiant stellar wind, and (iii) Roche lobe filling supergiants. I then report on the discovery of two new populations of HMXBs hosting supergiant stars, recently revealed by a wealth of new observations, coming from the high energy side (INTEGRAL, Swift, XMM, Chandra satellites), and complemented by multi-wavelength optical/infrared observations (mainly ESO facilities). The first population is constituted of obscured supergiant HMXBs, the second one of supergiant fast X-ray transients (SFXTs), exhibiting short and intense X-ray flares. I finally discuss the formation and evolution of HMXBs, constrain the accretion models (e.g. clumpy winds, transitory accretion disc, magneto-centrifugal barrier), show evidences suggesting the existence of an evolutionary link, include comparisons with population synthesis models, and finally build a consistent scenario explaining the various characteristics of these extreme celestial sources. Because they are the likely progenitors of Luminous Blue Variables (LBVs), and also of neutron star/black hole binary mergers, related to short/hard gamma-ray bursts, the knowledge of the nature, formation and evolution of these HMXB populations is of prime importance.