Usability is a key discipline related to the development of modern software systems. Its goal is to assess the user-friendliness and effectiveness of a software product from the user point of view. Therefore, proper methodologies and techniques to perform this assessment are definitely relevant. Heuristic evaluation is probably the most commonly used method for usability assessment. Developed initially by Nielsen and Molich in the 90s, traditional heuristic evaluations rely on Nielsen’s well-known 10 usability heuristics. However, recent evidence suggests that such heuristics are not sufficiently complete for dealing with new domains such as interactive television, virtual worlds, and many others. In addition to the lack of suitability of the traditional heuristics, it has been stated in the past years the lack of a robust methodology or process to effectively develop and validate these new domain-specific heuristics. In this paper we summarize current evidence regarding the lack of suitability of traditional heuristics, as well as the need for the development of new domain-specific heuristics. After identifying and acknowledging existing gaps in the state-of-the-art pointed by other researchers, we present PROMETHEUS, a PROcedural METhodology for developing HEuristics of USability. PROMETHEUS refines the methodology of Rusu et al. (2011), and is composed of 8 stages. PROMETHEUS clearly defines the artifacts that are required and produced by each stage, and also presents a set of quality indicators in order to assess the need for further refinement in the development of new heuristics. As an initial validation of PROMETHEUS, we apply a questionnaire to several researchers that have used the methodology of Rusu~etal, and we have also performed a small retrospective study, computing the quality indicators of several previous studies. Our results suggest that PROMETHEUS is a very promising methodology, and that the metrics and indicators are indeed pertinent with respect to the conclusions of previous works.