Born Yisrael Idelson in Konotop, in the Chernigov Governorate of the Russian Empire (present-day Sumy Oblast, Ukraine) in 1895, Bar-Yehuda attended an Academic High School and the Mine Engineering Institute in Ekaterinoslav. In 1909 joined Tze'irei Zion (later to be merged into Hashomer Hatzair) and was made a member of its central committee in Russia in 1917. He was Secretary of the Central Committee of the “Socialist Zionists”, where he met and married Beba Idelson (whom he would later divorce). In 1922 they were arrested by the Soviet authorities and exiled to Siberia. In 1924, thanks to an intercession by Maxim Gorki's wife, their banishment was converted to deportation to Mandate Palestine. They traveled to Lithuania and from there to Berlin by way of Danzig. For the next two years in Berlin they were active in establishing the World Union of Socialist Zionists and became the Movement's Secretary.
In 1926 he immigrated to Palestine. He was Secretary of the Petah Tikva Workers Council and organized sentries to protect Jewish workers. He also did roadwork on the Tel Aviv-Petah Tikva road. In 1930 he joined kibbutzYagur, and became its secretary six years later. During the 1936-39 Arab revolt he was among the first to call for "active defense".
He was a delegate to the Assembly of Representatives and a member of the Constituent Assembly. He was one of the leaders of the “B” faction in Mapai and one of the leaders of the Ahdut HaAvoda after the split in 1944. From 1960 to 1962 he was secretary general of Ahdut HaAvoda.