Abstract We consider the problem of map learning while maintaining ground-truth pose estimates. Map learning is important in tasks that require a model of the environment or some of its features. As a robot collects data, uncertainty about its position accumulates and corrupts its knowledge of the positions from which observations are taken. We address this problem by employing cooperative localization; that is, deploying a second robot to observe the other as it explores, thereby establishing a virtual tether, and enabling an accurate estimate of the robot's position while it constructs the map. This paper presents our approach to this problem in the context of learning a set of visual landmarks useful for pose estimation. In addition to developing a formalism and concept, we validate our results experimentally and present quantitative results demonstrating the performance of the method.