Born in Kafr Qasim, where his grandfather was murdered in the Kafr Qasim massacre, Frej is the eldest of twelve children. In 1982 he began studying accounting and economics at the Hebrew University of Jerusalem, and later worked as an accountant. Whilst at university he joined the joint Jewish-Arab campus group, and subsequently joined the Ratz party, which later merged into Meretz. He served on the secretariat of Peace Now and was involved in the Geneva Accord.
Frej first ran for the Knesset in 2003, and was placed sixteenth on the Meretz list for the elections that year. However, the party won only six seats. For the 2006 elections he was placed seventh, but Meretz won only five seats. In the 2009 elections he was placed ninth, but again failed to win a seat as Meretz was reduced to three MKs. However, after being placed fifth on the party's list for the 2013 elections, he entered the Knesset after the party won six seats. Frej was re-elected in the 2015 elections after being placed third on the Meretz list.