Born in Baghdad in Iraq, Cohen made aliyah in 1951. During his youth he was a counsellor in the HaNoar HaOved VeHaLomed youth movement, and was secretary of the Labor Party youth guard in Bnei Brak until 1970. He took Middle Eastern studies at Tel Aviv University, gaining a BA, MA and PhD in the subject. He served as chairman of Labor Party's Arab and Druze branch between 1975 and 1986. Between 1986 and 1992 he chaired the party's elections branch.
In 1988 he was elected to the Knesset on the Alignment's list. He was re-elected in 1992 (by which time the Alignment had merged into the Labor Party), and 1996. In December 1997 he was elected secretary-general of the party, winning 76% of the vote. He retained his seat in the 1999 elections (on the One Israel list), and in August 2000 was appointed Minister of Labor and Social Welfare in Ehud Barak's government following Shas' departure from the coalition government.