<p>Augmented reality (AR) systems are promising tools for navigation and wayfinding, but questions remain about optimal design and effectiveness. We developed an AR system to aid users’ navigation through a complex building. We then explored three research questions. First, we asked how handheld monoscopic and head-mounted stereoscopic optical see-through AR tools affect a user’s abilities to navigate an indoor environment for the first time, compared to a control group using no aid. We found that head-mounted stereoscopic optical see-through AR improved participants’ abilities to navigate a novel environment, relative to the control group, but participants using handheld monoscopic AR performed worse than the control group. Second, we asked how AR changed users’ abilities to navigate this indoor environment in future attempts without any technological assistance. When users were asked to navigate the environment for a second time, two weeks later, participants in all three groups significantly improved their performance. However, users in the control group improved the most. Third, we asked how improvements in navigational skill were related to users’ age, gender identity, and spatial thinking skill. We found significant relationships between participants’ age and navigational performance, and significant interactions between age and gender, but no relationship between spatial thinking ability and navigational performance. Within our sample (<i>n</i> = 76), we observed a clear benefit to using head-mounted stereoscopic optical see-through AR, but the handheld monoscopic AR hindered participants’ ability to navigate the indoor environment for the first time.</p>