Language has been linked to spatial representation and behavior in humans, but the nature of this effect is debated. Here, we test whether simple verbal expressions improve 4-year-old children's performance in a disoriented search task in a small rectangular room with a single red landmark wall. Disoriented children's landmark-guided search for a hidden object was dramatically enhanced when the experimenter used certain verbal expressions to designate the landmark during the hiding event. Both a spatial expression ("I'm hiding the sticker at the red/white wall") and a non-spatial but task-relevant expression ("The red/white wall can help you get the sticker") enhanced children's search, relative to uncued controls. By contrast, a verbal expression that drew attention to the landmark in a task-irrelevant manner ("Look at this pretty red/white wall") produced no such enhancement. These findings provide further evidence that language changes spatial behavior in children and illuminate one mechanism through which language exerts its effect: by helping children understand the relevance of landmarks for encoding locations.