Context :

Aims : To constrain models of high-mass star formation , the Herschel /HOBYS key program aims at discovering massive dense cores ( MDCs ) able to host the high-mass analogs of low-mass prestellar cores , which have been searched for over the past decade .
We here focus on NGC 6334 , one of the best-studied HOBYS molecular cloud complexes .

Methods : We used Herschel PACS and SPIRE 70 - 500 ~ { } \mu m images of the NGC 6334 complex complemented with ( sub ) millimeter and mid-infrared data .
We built a complete procedure to extract \sim 0.1 pc dense cores with the getsources software , which simultaneously measures their far-infrared to millimeter fluxes .
We carefully estimated the temperatures and masses of these dense cores from their spectral energy distributions ( SEDs ) .
We also identified the densest pc-scale cloud structures of NGC 6334 , one 2 pc \times 1 pc ridge and two 0.8 pc \times 0.8 pc hubs , with volume-averaged densities of \sim 10 ^ { 5 } cm ^ { -3 } .

Results : A cross-correlation with high-mass star formation signposts suggests a mass threshold of 75 ~ { } \mbox { $M _ { \odot } $ } for MDCs in NGC 6334 .
MDCs have temperatures of 9.5 - 40 K , masses of 75 - 1000 ~ { } \mbox { $M _ { \odot } $ } , and densities of 1 \times 10 ^ { 5 } -7 \times 10 ^ { 7 } cm ^ { -3 } .
Their mid-infrared emission is used to separate 6 IR-bright and 10 IR-quiet protostellar MDCs while their 70 ~ { } \mu m emission strength , with respect to fitted SEDs , helps identify 16 starless MDC candidates .
The ability of the latter to host high-mass prestellar cores is investigated here and remains questionable .
An increase in mass and density from the starless to the IR-quiet and IR-bright phases suggests that the protostars and MDCs simultaneously grow in mass .
The statistical lifetimes of the high-mass prestellar and protostellar core phases , estimated to be 1 - 7 \times~ { } 10 ^ { 4 } yr and at most 3 \times~ { } 10 ^ { 5 } yr respectively , suggest a dynamical scenario of high-mass star formation .

Conclusions : The present study provides good mass estimates for a statistically significant sample , covering the earliest phases of high-mass star formation .
High-mass prestellar cores may not exist in NGC 6334 , favoring a scenario presented here , which simultaneously forms clouds and high-mass protostars .