Spatial communication tasks, such as following route directions through unfamiliar environments, place considerable demands on multiple cognitive processes, including language comprehension and memory. Gestures accompanying spoken route directions may aide task performance by enhancing cognitive processes such as language and memory processing. It is not yet clear whether different kinds of gesture might influence the processing of route information in different ways. In 2 experiments, we examined how different gestures would enhance or reduce listeners' recall of spatial information when given route directions through an unfamiliar building. Adults were randomly allocated to one of three gesture conditions: no gesture (speech only), beat gesture (speech accompanied by simple rhythmic gestures), or iconic-deictic gesture (speech accompanied by iconic and deictic gestures). Recall was measured verbally, by recalling the route aloud, then physically, by walking the route. In Experiment 1, redundant gestures that mirrored verbal route directions did not enhance listeners' verbal recall or route navigation. In Experiment 2, when the verbal route directions were edited to be incomplete, nonredundant gestures enhanced recall to the level seen when hearing all information through speech. These findings suggest that gestures enhance recall when compensating for missing verbal information, but not when they replicate verbal information.