This paper proposes combining traditional usability methods with the analysis of eye movement recordings to evaluate interactive map interfaces, and presents a case study in support of this approach. This case study evaluates of two informationally equivalent but differently-designed online interactive map interfaces presented to users. In a mixed factorial experiment thirty participants were asked to solve three typical map use tasks using one of the two interfaces, while we measured user Satisfaction, Efficiency (completion time) and Effectiveness (accuracy) with standard SEE usability metrics. While traditional (bottom line) usability metrics can reveal a range of usability problems, they may be enhanced by additional procedural measures such as eye movement recordings. Eye movements have been shown to reveal the amount of cognitive processing a display requires and where these cognitive resources are required. Therefore, we can establish how a display may or may not facilitate task completion by analyzing eye movement recordings. User satisfaction information related to stimuli (i.e., collected through standardized questionnaires) can also be linked to eye tracking data for further analysis. We hope that the presented methodology and case study will help cartographers and map interface designers to better identify design issues in their products, and that these insights will eventually lead to more effective and efficient online map interfaces.