He began his political career when elected to the Haifa Labor Council in 1964, a position he retained until 1971. Between 1964 and 1969, he was also a member of Haifa City Council. For the 1969 Knesset elections he was placed 57th on the Alignment's list, but missed out when the alliance won only 56 seats. Nevertheless, Shahal entered the Knesset on 1 September 1971 as a replacement for the deceased Mordechai Ofer.
Although he retained his seat in the 1996 elections and Labour remained the largest party, Benjamin Netanyahu's Likud formed the government, and Shahal lost his place in the cabinet. He resigned from the Knesset on 20 March 1998 and was replaced by Rafik Haj Yahia.
Whilst serving as an MK, Shahal was a permanent observer to the Council of Europe (1974–76) and a permanent representative to the Inter-Parliamentary Union (1976–84). Outside the Knesset, he also served as a chairman of the Israel Consumer's Council.