When making decisions, we sometimes rely on habit and at other times plan towards goals. Planning requires the construction and use of an internal representation of the environment, a cognitive map. How are these maps constructed, and how do they guide goal-directed decisions? We coupled a sequential decision-making task with a behavioral representational similarity analysis approach to examine how relationships between choice options change when people build a cognitive map of the task structure. We found that participants who encoded stronger higher-order relationships among choice options showed increased planning and better performance. These higher-order relationships were more strongly encoded among objects encountered in high-reward contexts, indicating a role for motivation during cognitive map construction. In contrast, lower-order relationships such as simple visual co-occurrence of objects did not predict goal-directed planning. These results show that humans actively construct and use cognitive maps of task structure to make goal-directed decisions.