Representing relational knowledge in a mental map is useful for adaptive behaviour. Here, we studied how curriculum learning (the use of different training regimes) influences the way that mental (or ‘cognitive’) maps are formed. We investigated how the order in which people learned one-step transitions impacted their subsequent ability to perform multi-step inference using the cognitive maps they had formed. Participants learned one map with a curriculum that grouped information by rows and columns (‘grouped curriculum’) and another that selected transitions for training in a spatially disjoint way (‘disjoint curriculum’). Subsequent multi-step navigation was performed better after training using the disjoint curriculum. We hypothesise that learning under a grouped curriculum results in mental fragmentation of the learned maps, which impairs subsequent navigation across rows and columns. By contrast, learning one-step transitions in a pseudo-random order facilitates subsequent integration of learned information into a mental map to enable adaptive behaviour.