Prior to his entry in national politics, Malik had served in the FIA as a special agent, eventually becoming the Additional Director General of the Federal Investigation Agency in 1993 until 1996.

During his stint as Director, he coordinated successful counter-terrorist operations in the country as well as abroad, including the arrest and extradition of Yousaf Ramzi to the United States in 1995.

[10] Over this issue, the teachers society of Karachi University passed a unanimous resolution demanding the Governor of Sindh and the Vice Chancellor revoke the honorary doctorate degree.

[11][12] In 1973, Malik joined the National Alien Registration Authority (NARA) as the immigration agent and subsequently served in the various services of the intelligence community, working in various criminal offense cases.

[13] As Director of the FIA, Malik launched a secret war against the Islamist elements in Pakistan, which amounted to a direct attack on the Inter-Services Intelligence (ISI).

[14] His efforts equally dismayed the military establishment by reports of the FIA contacting the Israeli secret service, the Mossad, to investigate Islamist terrorists.

The FIA leadership under Malik also angered Taliban supporters within the conservative establishment, because they allowed the extradition of Ramzi Yousef to the United States for trial on the 1993 World Trade Center bombing.

[14] One of the first acts of President Leghari, after dismissing Prime Minister Benazir Bhutto on 5 November 1996, was to imprison Ghulam Asghar, Director General of the FIA, on non-specified corruption charges.

[16] With the dismissal of the government of the PPP, Malik left the country and settled in the United Kingdom, where he set up his own private security firm, DM Digital Network.

[22][23] Former Interior Minister Senator A. Rehman Malik was awarded Sitar e Shujat for his bravery as FIA officer in his valiant actions against criminals and terrorists and Nishan-e-Imtiaz for his unmatched services for the country and its people.

After PPP formed the Federal Government following the 2008 general elections, Malik was appointed an "adviser on interior, intelligence, and narcotics control" by Prime Minister Yousaf Gillani.

[13] In a research analysis printed in Dawn newspaper, his stint as Interior Minister was criticized over the issues of target killings in Sindh and the security aftermath of the Afghanistan war.

[13] Interior Minister Malik has offered a $1 million bounty for the capture of Ehsanullah Ehsan (Isanullah Isan), the Pakistani Taliban spokesman who had attempted to try and justify the shocking October 2012 attempted assassination (and further threats on the life) of the 14-year-old Pakistani female blogger Malala Yousafzai (Yousafzai), a native of the Mingora region of the Swat Valley who had campaigned for the human and educational rights of girls and women in Pakistan and beyond, to international acclaim.

[27] Effectively, the Chief Justice Iftikhar Chaudhry suspended the electoral membership of Malik when he had shown reluctance to submit a declaration by the United Kingdom's Border Agency to establish that his client had surrendered British nationality on 6 June 2012.