Haq was born in Seydan, Afghanistan, a small village in Nangarhar province, although he soon moved with his family to Helmand. His father, Mohammed Aman, was the representative in Helmand for a Nangarhar construction company, and was relatively wealthy by Afghan standards. His family was well connected, part of the Arsala Khel family, which is a part of the Jabar Khel (a subtribe of the land-owning Ahmadzai tribe). They are all ethnic Pashtuns. His paternal great-grandfather, Wazir Arsala Khan, had once been the foreign minister of Afghanistan; a cousin, Hedayat Arsala, was a World Bank director working in Washington, D.C. who later became Vice President of Afghanistan in Hamid Karzai's administration.
Haq also had two older brothers (Haji Din Mohammad and Abdul Qadir), and one younger brother (Nasrullah Baryalai Arsalai). Abdul Qadir was an early backer of Hamid Karzai, who was rewarded with a cabinet position, before he was assassinated in 2002. Haji Din Muhammad is the leader of the Hezb-e Islami Khalis party.
From his own account, Haq was an unruly child, who after persuading his father to register him for school at the early age of five, once hit a teacher who was sleeping on the job. A year after that his 51-year-old father died of kidney disease, prompting Din Mohammad to assume leadership of the family, and prompting the family to move back to their extended family in Nangarhar.
Back in Fatehabad, Haq began attending Koranic school under the tutelage of local mullahs, and once reaching the age of eight, began studying at the lycée. It was here where he started challenging the Communist ideology of some of his teachers.
Haq first engaged in the fight against the Afghan government in 1977, initially without external support, then with the Hizb-i-Islami faction led by Mohammad Yunus Khalis - not to be mistaken with the Hezb-i-Islami faction of Gulbuddin Hekmatyar. During the Soviet war in Afghanistan, Haq coordinated mujahideen activities in the province of Kabul. He gained recognition for his tactical skills and bravery, and his reputation as a unifier led to leadership positions throughout Afghanistan.
Haq was one of the CIA's few Afghan contacts in the early years of the war; Coll writes that he "grew to become Howard Hart's most important Afghan guide to the anti-Soviet war." Later in the 1980s he became a critic of ISI and (after his relationship with them ended) the CIA. The CIA labelled him Hollywood Haq - the Hollywood Commander.
Haq was injured several times, including the loss of part of his right heel. Because of his injuries, he often fought battles against the Soviets from horseback.
Haq was the cabinet minister for internal security in the Islamic State of Afghanistan which had been created by the peace and power-sharing agreement Peshawar Accord after the fall of the communist Najibullah regime in April 1992. Gulbuddin Hekmatyar, who had been offered the position of prime minister, refused to share power with other parties and started a massive bombardment campaign against the capital Kabul. Hekmatyar's attacks led to prolonged war in Afghanistan. In the following period Haq resigned as interior minister to leave Afghanistan and settle in Dubai, where it was reported he became a successful merchant.
In 1998, he became a United Nations Peace Mediator.
In January 1999, unknown assailants killed Haq's watchman, entered his home, and murdered his wife and son in Hayatabad. Another of Haq's sons survived the raid.
From 1999 onwards a process was set into motion by Ahmad Shah Massoud and Haq to unite the ethnicities of Afghanistan against the Taliban regime. Massoud united the Tajiks, Hazara and Uzbeks as well as several Pashtun commanders. Besides meeting with Pashtun tribal leaders and acting as a point of reference, Haq received increasing numbers of Pashtun Taliban themselves who were secretly approaching him. Some commanders which had worked for the Taliban military apparatus agreed to the plan to topple the Taliban regime as the Taliban lost support even among the Pashtuns. Senior diplomat and Afghanistan expert Peter Tomsen hoped that "[t]he ‘Lion of Kabul’ [Abdul Haq] and the ‘Lion of Panjshir’ [Ahmad Shah Massoud] would make a formidable anti-Taliban team if they combined forces. Haq, Massoud, and Karzai, Afghanistan's three leading moderates, could transcend the Pashtun—non-Pashtun, north-south divide." The senior Hazara and Uzbek leaders took part in the process just like later Afghan president Hamid Karzai. They agreed to work under the banner of exiled Afghan King, Zahir Shah, who was residing in Rome, Italy.
In November 2000, leaders from all ethnic groups were brought together in Massoud's headquarters in northern Afghanistan traveling from other parts of Afghanistan, Europe, the United States, Pakistan and India to discuss a Loya Jirga for a settlement of Afghanistan's problems and to discuss the establishment of a post-Taliban government. In September 2001 an international official who met with representatives of the alliance would remark, "It's crazy that you have this today ... Pashtuns, Tajiks, Uzbeks, Hazara ... They were all ready to buy in to the process".
Following the al-Qaeda attacks of September 11, 2001 against the United States, Haq entered eastern Afghanistan from Pakistan's Khyber Pakhtunkhwa to implement his resistance plan against the Taliban. Some sources have speculated that the CIA supported this initiative but family members and other witness sources have denied this claim writing that the CIA actually urged him not to enter Afghanistan. Former CIA director George Tenet reports that, at the recommendation of Bud McFarlane, CIA officials met with Haq in Pakistan and after assessing his capabilities urged him not to enter Afghanistan. After a chase, he was captured by the Taliban along with nineteen others between the towns of Hisarak and Azro in Nangarhar province, and was killed on October 26, 2001. The Guardian speculates that his capture was due to a betrayal by double agents. Some reports soon after his death blamed the CIA for siding too closely with Pakistan's ISI, which did not wish to see Afghans united across ethnic lines, and for failing to intervene to rescue him from his Taliban captors. This version was solidified by reports of tension between Haq and American agents after an interview in which he stated "...we cannot be [America's] puppet." He was one of many Afghan rebel leaders opposed to the U.S. intervention.
An obituary in The Guardian called Abdul Haq an "astute leader", and one of the few Afghans capable of working to bring together a working pan-ethnic loya jirga.