Benayoun begon met voetballen bij Hapoel Dimona, waarna hij overstapte naar Hapoel Beër Sjeva. Op zijn vijftiende werd hij gescout door AFC Ajax en naar Amsterdam gehaald. Op zijn zestiende was hij een topscorer van zijn team. Ajax bood hem een vierjarig contract aan, maar vanwege heimwee en het niet in Nederland kunnen aarden van zijn familie, keerde hij terug naar zijn geboorteland.
Op 22-jarige leeftijd ging hij opnieuw de grens over, naar Racing Santander. Benayoun was van 2002 tot 2005 een vaste waarde in het team van de Cantabrische club. Hij speelde in deze periode bij Racing samen met zijn landgenoten verdedigers Omri Afek en Ilan Bakhar en doelman Dudu Aouate. In het seizoen 2005/2006 vertrok hij naar West Ham United om ten slotte in de zomer van 2007 naar Liverpool over te stappen.
In 2010 maakte Benayoun transfervrij de overstap van Liverpool naar concurrent Chelsea FC. In de eerste helft van het seizoen 2012/13 kwam hij uit voor West Ham United FC op uitleenbasis. In januari 2013 keerde hij terug naar Chelsea.