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 μm images of the NGC 6334 complex complemented with (sub)millimeter and mid-infrared data. We built a complete procedure to extract ~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 × 1 pc ridge and two 0.8 pc × 0.8 pc hubs, with volume-averaged densities of ~105 cm-3. Results. A cross-correlation with high-mass star formation signposts suggests a mass threshold of 75 M⊙ for MDCs in NGC 6334. MDCs have temperatures of 9.5−40 K, masses of 75−1000 M⊙, and densities of 1 × 105−7 × 107 cm-3. Their mid-infrared emission is used to separate 6 IR-bright and 10 IR-quiet protostellar MDCs while their 70 μ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 × 104 yr and at most 3 × 105 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, ridges, MDCs, and high-mass protostars.