In this paper, a set of heuristics for evaluating the usability of mobile map applications is introduced. We developed the heuristics by exploring the present generic heuristics and then forming new theory-based heuristics. Usability specialists tested the heuristics by evaluating the usability of a mobile map application with both generic and domain-specific heuristics. As a result, more usability problems were found with the proposed domain-specific heuristics. In addition, based on the evaluators’ views the initial domain-specific heuristics were further developed. We conclude by proposing domain-specific usability heuristics for evaluating the mobile map applications.