This investigation examined whether children can code the relative proximity of two objects to a landmark and whether they use verbal or nonverbal strategies to remember a target location. Two- to 2.5-year-olds completed a memory task where they watched an experimenter hide two different toys in two identical containers placed 2 and 12 inches from a landmark. The experimenter either used neutral language (e.g., “here”; Experiment 1) or spatial labels (e.g., “close/far”; Experiment 2) to describe objects’ hiding locations. After hiding, children were carried outside the enclosure to a new viewpoint during a 10-second delay and then looked for a target toy. Experiment 2 also included language measures: parent reports of children’s general and relational vocabularies and performance on a language task, which measured children’s understanding of spatial (close/far) and color (red/blue) terms. We found that children successfully coded relative to proximity to a landmark in the memory task. However, hearing spatial labels during hiding in Experiment 2 did not improve performance relative to Experiment 1, and children’s spatial term comprehension in the language task did not predict memory task performance. We also found that children’s productive relational vocabulary predicted memory task performance; however, children’s color term comprehension in the language task was the strongest overall predictor of memory task performance. Collectively, these results suggest that children initially rely on a nonverbal strategy when coding relative proximity to a landmark in a memory task and that children who are better at forming abstract categories may code relative proximity more successfully.