Eliyahu grew up in the youth system of Maccabi Ironi Ramat Gan, but moved to Galil for the 2004–05 season, in order to further his career. The move paid off when, under the guidance of Oded Katash, Eliyahu made great strides in improving his game. After the 2005–06 season, Eliyahu entered the 2006 NBA Draft, a move criticized by Hanoch Mintz, Eliyahu's coach during his time in Ramat Gan.
In pre-draft camps in Europe, Eliyahu impressed along with fellow Israeli Yotam Halperin and when the camp was finished in Treviso, Italy, both had dramatically climbed the mock draft charts. On June 28, 2006, he made national headlines in Israel by being selected by the Orlando Magic with the 44th pick of the 2006 NBA Draft. He was later traded to the Houston Rockets for cash considerations. He also impressed during matches of Maccabi against NBA teams. During the Euroleague 2006-07 season, Eliyahu averaged 10.8 points per game.
In December 2008, Eliyahu became the first Israeli to be named the MVP of the Euroleague for a month during the season. He recorded a double double in all three games he played during December. Overall for the 2008–09 Euroleague season, Eliyahu averaged 14.0 points and 6.6 rebounds per game. In 2009, Eliyahu signed a 4-year contract worth €6 million euros net income with the Spanish League club Caja Laboral and won Spanish national championship with his new team in 2010 scoring 18 points in the deciding game against Euroleague champions Barcelona.