Shahidan was a Member of Parliament for Arau from 1986 to 1995. He was elected to the Perlis State Legislative Assembly for the newly created seat of Tambun Tulang in the 1995 general elections. He immediately became Chief Minister of Perlis, taking over from Hamid Pawanteh. His tenure as Chief Minister came to an end in March 2008, when Md Isa Sabu, a fellow member of Barisan Nasional, was appointed to the post by Raja Sirajuddin of Perlis after a general election in which UMNO retained its majority in the State Assembly. Md Isa claimed the support of eight out of the 12 other Barisan Nasional members of the Perlis State Assembly to replace Shahidan. While Shahidan had the nomination of the Prime Minister, Abdullah Badawi, and the state party machinery, the Raja was concerned about the stability of the state government should Shahidan, a powerful but divisive factional figure in UMNO, be reappointed. The Raja insisted upon appointing Md Isa instead, exercising his constitutional discretion to prevail over the wishes of Abdullah and UMNO. Shahidan left the Perlis Executive Council, sitting out the 2008–13 State Assembly term as a backbencher and criticising Md Isa's leadership. In the 2013 general elections, Shahidan returned to federal Parliament in the seat of Arau, switching seats with his brother Ismail Kassim, who had held Arau since 2008. Shahidan defeated the senior Pan-Malaysian Islamic Party leader Haron Din by 1,371 votes. Despite his return to federal politics, Shahidan had stated before the election that his preference would have been to remain in the State Assembly. After the election, he was appointed to the cabinet of Najib Razak as a Minister in the Prime Minister's Department.
Views and comments on various issues
According to Joceline Tan, columnist for The Star, Shahidan has a "larger-than-life personality" and is known for his "warlord style of politics". He has held numerous positions in sports administration, including the presidencies of the Malaysia Athletic Federation, the Amateur Swimming Union of Malaysia and the Perlis Football Association. In 2010, he called for Facebook to be banned in Malaysia, citing national security issues after a Facebook account holder was found to have insulted Islam and the current as well as the former Prime Ministers of Malaysia. In 1992, he received international coverage for his criticism of what he cited as the criminal acts of Sultan Iskandar of Johor and his son Tunku Ibrahim Ismail. Shahidan is a leading proponent of Salafism—a puritanical Sunni Islamic movement opposed by Malaysia's religious establishment—within UMNO. In 2010 he arranged for a group of young Salafi clerics, including Fathul Bari Mat Jahya, to join UMNO to boost the party's standing with conservative Muslim voters. While Chief Minister of Perlis, his government passed anti-apostasy laws in the State Assembly and sought to loosen restrictions on polygamy in the state. In 2017, Shahidan declared that "atheism is against the Constitution and the basic human rights" in Malaysia since "there is no provision on atheism" in the Constitution. Shahidan wanted atheists and atheist groups like the Kuala Lumpur chapter of Atheist Republic to be identified and hunted down. He also stated that "we need to restore the faith back in them, especially for Muslims. Actually they don't really want to be an atheist, but they lack knowledge about religion and that is why they are easily swayed to the new age teaching".
