To constrain models of high-mass star formation, the Herschel/HOBYS KP 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 NGC6334, one of the best-studied HOBYS molecular cloud complexes. We used Herschel PACS and SPIRE 70-500mu images of the NGC6334 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 SEDs. A cross-correlation with high-mass star formation signposts suggests a mass threshold of 75Msun for MDCs in NGC6334. MDCs have temperatures of 9.5-40K, masses of 75-1000Msun, and densities of 10^5-10^8cm-3. Their mid-IR emission is used to separate 6 IR-bright and 10 IR-quiet protostellar MDCs while their 70mu 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-7x10^4yr and at most 3x10^5yr respectively, suggest a dynamical scenario of high-mass star formation. 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 NGC6334, favoring a scenario presented here, which simultaneously forms clouds and high-mass protostars.