During early childhood, children find spatial tasks such as following novel route directions challenging. Spatial tasks place demands on multiple cognitive processes, including language comprehension and memory, at a time in development when resources are limited. As such, gestures accompanying route directions may aid comprehension and facilitate task performance by scaffolding cognitive processes, including language and memory processing. This study examined the effect of presenting gesture during encoding on spatial task performance during early childhood. Three- to five-year-olds were presented with verbal route directions through a zoo-themed spatial array and, depending on assigned condition (no gesture, beat gesture, or iconic/deictic gesture), accompanying gestures. Children presented with verbal route directions accompanied by a combination of iconic (pantomime) and deictic (pointing) gestures verbally recalled more than children presented with beat gestures (rhythmic hand movements) or no gestures accompanying the route directions. The presence of gesture accompanying route directions similarly influenced physical route navigation, such that children presented with gesture (beat, pantomime, and pointing) navigated the route more accurately than children presented with no gestures. Across all gesture conditions, location information (e.g., the penguin pond) was recalled more than movement information (e.g., go around) and descriptive information (e.g., bright red). These findings suggest that speakers’ gestures accompanying spatial task information influence listeners’ recall and task performance.