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 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 ...