Gestures are important non-verbal signals in human communication. Research with virtual agents and robots has started to add to the scientific knowledge about gestures but many questions with respect to the use of gestures in human-computer interaction are still open. This paper investigates the influence of robot gestures on the users' perceived workload and task performance (i.e. information recall) in a direction-giving task. We conducted a 2 x 2 (robot gestures vs. no robot gestures x easy vs. difficult task) experiment. The results indicate that robot gestures increased user performance and decreased perceived workload in the difficult task but not in the easy task. Thus, robot gestures are a promising means to improve human-robot interaction particularly in challenging tasks.