Usability is used to assess the effectiveness of a software product from the user point of view. Hence, proper methodologies and techniques to perform this assessment are very relevant. Heuristic evaluation is probably the most commonly used method for usability assessment. Developed by Nielsen and Molich in the '90s, traditional heuristic evaluations rely on Nielsen's 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 traditional heuristics, in the past years the lack of a robust methodology or process to effectively develop and validate these new domain-specific heuristics has been documented. In this paper we summarize current evidence on the lack of suitability of traditional heuristics, as well as the need to develop new domain-specific heuristics. After identifying and acknowledging existing gaps in heuristics for state-of-the-art technology, 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 et. al., 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 studies.