Co-verbal gestures, the spontaneous gestures that accompany human speech, form an integral part of human communications; they have been shown to have a variety of beneficial effects on listener behaviour. Therefore, we suggest that a humanoid robot, which aims to communicate effectively with human users, should gesture in a human-like way, and thus engender similar beneficial effects on users. In order to investigate whether robot-performed co-verbal gestures do produce these effects, and are thus worthwhile for a communicative robot, we have conducted two user studies. In the first study we investigated whether users paid attention to our humanoid robot for longer when it performed co-verbal gestures, than when it performed small arm movements unrelated to the speech. Our findings confirmed our expectations, as there was a very significant difference in the length of time that users paid attention between the two conditions. In the second user study we investigated whether gestures performed during speech improved user memory of facts accompanied by gestures and whether they were linked in memory to the speech they accompanied. An observable affect on the speed and certainty of recall was found. We consider these observations of normative responses to the gestures performed, to be an indication of the value of co-verbal gesture for a communicative humanoid robot, and an objective measure of the success of our gesturing method.