Cognitive maps confer animals with flexible intelligence by representing spatial, temporal, and abstract relationships that can be used to shape thought, planning, and behavior. Cognitive maps have been observed in the hippocampus, but their algorithmic form and the processes by which they are learned remain obscure. We employed large-scale, longitudinal two-photon calcium imaging to record activity from thousands of neurons in the CA1 region of the hippocampus while mice learned to efficiently collect rewards from two subtly different linear tracks in virtual reality. The results provide a detailed view of the formation of a cognitive map in the hippocampus. Throughout learning, both the animal behavior and hippocampal neural activity progressed through multiple intermediate stages, gradually revealing improved task representation that mirrored improved behavioral efficiency. The learning process involved progressive decorrelations in initially similar hippocampal neural activity within and across tracks, ultimately resulting in orthogonalized representations resembling a state machine capturing the inherent structure of the task. This decorrelation process was driven by individual neurons acquiring trial-type specific responses (i.e., ‘state cells’). Although cognitive maps are thought to support future prediction, orthogonalized representations do not automatically emerge in artificial neural networks predicting future observations. Interestingly, Clone-Structured Cognitive Graph (CSCG), a specific type of Hidden Markov Model, trained to maximize the probability of observed sequences not only captures the final orthogonalized structure but also replicates key aspects of the learning trajectory. We further demonstrate that mice exhibited adaptive behavior in novel task settings, with neural activity reflecting flexible deployment of the state machine. These findings shed light on the algorithmic form of cognitive maps, the learning rules that sculpt them, and the way that these maps promote adaptive behavior in animals. The work thus charts a course toward a deeper understanding of biological and artificial intelligence.