In the General Elections of 2002, he was elected a member of the Grand National Assembly of Turkey representing Ankara for the AKP[2] and later he became a minister of state in Erdoğan's first cabinet following President Ahmet Necdet Sezer's veto of a proposal to appoint Atalay as minister of education. Then in August 2007 he was appointed interior minister, one of the few cabinet changes following the re-election of Prime Minister Recep Tayyip Erdoğan that summer, and also following Sezer's retirement from the presidency. In 2009, he was assigned with the task to find a solution to the Turkish Kurdish conflict, a project which lasted until December 2009 and was not supported by the Republican People's Party (CHP) and the Nationalist Movement Party (MHP).[3] In 2011, he was named deputy prime minister with the responsibility of human rights and the fight against terrorism and served in the post until 2014. He was re-elected to the Turkish Parliament in the general elections of November 2015, this time representing the province of Van for the AKP,[4] but did not stand as a candidate in 2018.[1]