Spatial navigation is a complex and multi-faceted skill that, in humans, is understood to encompass two distinct navigational strategies, namely allocentric and egocentric navigation. These differ in the frame of reference used and the brain networks activated. However, egocentric navigation can be further divided into two, equally distinct strategies depending on whether the navigator is using subject-to-object relations (egocentric-cue) or direction of body turns (egocentric-response) to navigate. To date, there are no experimental paradigms able to distinguish between participants’ employment of allocentric, egocentric-cue and egocentric-response strategies, and to track their usage over time. The current study presents the Hex Maze: a novel virtual environment that can not only distinguish between the three navigational strategies, but can also be used to index aspects of strategy use such as preference, acquisition, stability and competence. To illustrate this, 32 male and 32 female participants were presented with the Hex Maze and sex differences in strategy usage were explored. While the results offer some support for previously identified sex differences in strategy preference, there were no significant sex differences in the novel measures of strategy acquisition, stability, or multi-strategy competence. Additionally, our results suggest that strategy preference does not preclude learning to competently navigate using other strategies. Importantly, the current study offers validation for the Hex Maze as an unbiased method of exploring spatial navigation, and it is anticipated that this easy-to-use tool will be valuable across research and clinical settings.