One approach to explaining the conditions under which additional landmarks will be learned or ignored relates to the nature of the information provided by the landmarks (i.e., distance versus bearings). In the current experiment, we tested the ability of such an approach to explain the search behavior of human participants in a virtual landmark-based navigation task by manipulating whether landmarks provided stable distance, stable direction, or both stable distance and stable direction information. First, we incrementally shaped human participants’ search behavior in the presence of two ambiguous landmarks. Next, participants experienced one additional landmark that disambiguated the location of the goal. Finally, we presented three additional landmarks. In a control condition, the additional landmarks maintained stable distances and bearings to the goal across trials. In a stable bearings condition, the additional landmarks varied in their distances but maintained fixed bearings to the goal across trials. In a stable distance condition, the additional landmarks varied in their bearings but maintained fixed distances to the goal across trials. Landmark stability, in particular, the stability of landmark-to-goal bearings, affected learning of the added landmarks. We interpret the results in the context of the theories of spatial learning that incorporate the nature of the information provided by landmarks.