Benayoun var án efa efnilegasti leikmaður Ísraela þegar hann kom til ungalingaakademíu Ajax þegar hann var 15 ára gamall. Hann tók alla fjölskyldunameð en hún aðlagaðist ekki lífinu í Hollandi. Benayoun hreif forráðarmenn Ajax en þrátt fyrir að félagið vildi bjóða honum fjögurra ára samning hélt hann heim til Ísrael eftir aðeins eins árs dvöl í Amsterdam. Hann gekk til liðs við heimalið sitt, Hapoel Beer Sheva, og þrátt fyrir að liðið félli úr efstu deild var hann ein af stjörnum liðsins og skoraði 15 mörk á sínu eina tímabili hjá félaginu.
Benayoun var seldur til eins af frægustu liðum Ísraels, Maccabi Haifa, þar sem hann blómstraði hjá félaginu og með landsliðinu. Hann var valinn leikmaður ársins 2000-2001 tímabilið þegar Maccabi vann fyrsta meistaratitill sinn í sjö ár og félagið hampaði titlinum einnig ári síðar. Benayoun fannst þá tímabært að reyna sig utan heimalandsins á ný og hélt árið 2003 til Norður-Spánar til Racing Santander. Hann varð stjarna liðsins sem barðist jafnan fyrir tilverurétti sínum í Úrvalsdeildinni og gott orðspor fór af honum sem Rafa tók vel eftir. Eftir 101 deildarleik og 21 mark varð Santander að selja hann til að leysa úr fjárhagsvandræðum sínum.
West Ham keypti hann á tvær og hálfa milljón punda sumarið 2005. Hann skoraði fimm mörk og lagði upp sjö á fyrra ári sínu hjá Hömrurum og liðið lauk leiktíðinni í 9. sæti og komst í úrslit ensku bikarkeppninnar gegn Liverpool þar sem hann fór á kostum og tætti vörn Rauða hersins í sig. Þessi frammistaða varð örugglega framar öðrum að Rafa fékk hann til liðs við Liverpool ári síðar.