In subterranean species where excavation is energetically expensive, efficient spatial navigation is vital to reducing the costs of locating important resources such as food and mates. While spatial navigational ability is positively correlated with sociality in subterranean mammals, we have a less clear understanding of the role of habitat complexity on navigational ability. We tested spatial navigational ability and memory in 12-18-month captive Natal mole-rats (Cryptomys hottentotus natalensis) maintained in a simple environment with no environmental enrichment and newly captured wild individuals from natural, complex burrow systems. In maze trials, mole-rats captured freshly from the wild made significantly fewer navigational errors, were more likely to successfully navigate the maze, travelled shorter distances and as a consequence, completed the maze in less time. Male mole-rats from both experimental treatments were more likely to complete the maze than females. Memory retention of the maze was tested on day two, seven, 30 and 60, respectively. The results were variable, although both groups showed a significant memory retention 60 days after testing. Our results highlight the potential importance of the environment (microhabitat complexity) on spatial cognitive performance in mole-rats.