"В девятилетнем возрасте все признали его талант. В 11 лет назвали гениальным. А когда футболисту исполнилось 13, то его фото частенько публиковалось на обложках журналов в Израиле" - написал Джейсон Бёрт о Бенаюне для издания The Independent

Бенаюн начал карьеру футболиста в девятилетнем возрасте в клубе "Хапоэль Беер Шева". Позже игрок в поле зрения скаутов Аякса и даже получил предложение 4-летнего контракта. Он согласился и провел в Голландии один год, после чего по семейным обстоятельствам был вынужден вернуться в Израиль. Он подвергся резкой критике, основанной на том, что Йосси никогда не реализует свой потенциал. Он присоединился к местной команде Апоэль Беер Шева, и пока она боролась за выживание в элите, молодой Бенаюн блистал в ее составе и забил 15 голов в сезоне. Йосси казалось, что он спас свою команду от вылета, забив в последнем туре на 90-й минуте, но соперники также забили, и Апоэль покинул высший дивизион. Фото Бенаюна, только узнавшего о вылете родной команды, до сих пор вызывает слезы болельщиков.

Он перешел в Маккаби из Хайфы, где цветок Бенаюна расцвел по-настоящему, как на клубном, так и на национальном уровне. Он был избран игроком года в сезоне, в котором Маккаби впервые за семь лет выиграли первенство Израиля. В 2003 полузащитник перебрался на север Испании, в клуб Расинг Сантадер. Проведя там 101 матч лиги и забив 21 гол, он заработал репутацию одного из лучших игроков Испании. Позже клуб столкнулся с финансовыми проблемами, и Бенаюн был вынужден сменить клуб.

Вест Хэм не пожалел за израильтянина 2,5 миллиона фунтов, и в сезоне 2005-06, когда Вест Хэм финишировал на довольно приличном девятом месте, он забил 5 голов и сделал 6 результативных передач. Он показал неверотяно техничный футбол, что не могло не впечатлить менеджера "Красных" Рафы Бенитеса, и он настоял на его трансфере.

Первый его сезон на "Энфилде" был доовльно успешным для него: из 59 матчей сезона Бенаюн провел 47 игр, 12 раз был заменен сам и 21 выходил на замену. 11 голов при таких обстоятельствах были скорее хорошим результатом, особенно если учесть его позицию. Стоит среди этих голов отметить два хет-трика: в ворота клуба Хэвэнт и Уотерлувилл в рамках Кубка Англии, а также в ворота Бешикташа.

А вот дебютировал он в матче квалификации Лиги Чемпионов против Тулузы, а вот дебют в лиге пришелся на разгром клуба Дерби Каунти спустя несколько недель. И хотя для него, как и для всех игроков проводить матчи "на скамейке" довольно разочаровывающе, Йосси доказал, что он настоящий супер-саб. Его выход всегда менял ход игры. В матче с Уиганом, например, он вышел в начале второго тайма и забил победный гол через двадцать минут. Также он сумел доказать важность нахождения "в нужное время в нужном месте", особенно оформив два хет-трика: по меньшей мере половину из тех 6 голов он забил последним касанием.

Бенаюн продолжал прогрессировать, и с апреля 2009 он стал полноценным основным игроком. Его навыки обращения с мячом, а также скорость привели к этому.В 42 матчах он забил 9 голов в сезоне 2008-09. 6 июля 2009 года он продлил контракт с "Красными" до 2013 года.

Очередной прогресс ожидал его в начале сезона 2009-10. Он был одним из наиболее популярных и одним из наиболее эффективных. Йосси провел 29 матчей, в 22 из которых был заменен. 16 раз он появился со скамейки запасных. 9 раз вратарям соперников приходилось вытаскивать мяч из сетки своих ворот после ударов Бенаюна. Для игрока его позиции, особенно в Англии, это высокий показатель.

По окончании сезона будущее Йосси стало вызывать немало вопросов, особенно, подписание нового контракта Рафой Бенитесом. Среди претендентов на него называли лондонский Челси. 2 июля 2010 года он официально покинул Ливерпуль и присоединился к "Пенсионерам". Сумма сделки не разглашалась.