Hayfa yakınlarındaki Tantura’da 1929 yılında doğmuştur. Kudüs’teki Arap Kolejinde öğrenim görmüş ve bu kurumdan 1947 yılında mezun olmuştur. İngiliz Manda Yönetimi ve siyonist kuvvetlere karşı 1947-1948 yılları arasında Yafa’daki Filistin direnişine katılmıştır. 1948-1949 yılları arasında Filistin-Arap Kurtuluş Ordusu’nda, 1949-1958 yılları arasında ise Suriye Ordusunda hizmet etmiştir. Diplomasını ise 1952 yılında Humus’ta bulunan Suriye  Askeri İlimler Bölümünden almıştır. 1961-1964 yılları arasında Suriye’deki Filistinli Mülteciler Genel Müdürlüğünde genel müdür yardımcısı olarak çalıştı. 1963-1967 yılları arasında Şam Üniversitesinde Coğrafya, İşletme ve İstatistik Bölümlerinde uzmanlaşarak eğitimini tamamladı. Ardından Şam’da askeri bilimler alanında yüksek lisans  yaptı. 1964 yılında FKÖ’ye katıldı ve FKÖ tugaylarına bağlı olan Hıttin Kuvvetleri’ne 1967-1968 yılları arasında komutanlık yaptı. 1968 yılından itibaren FKÖ İcra Komitesine askeri danışmanlık yapmıştır. 1968 yılından 1971 yılına kadar FKÖ’nün genelkurmay başkanlığını üstlenmiştir. Ayrıca 1968-1969’da Filistin Planlama Merkezinde askeri danışman olarak çalıştı. 1968’den itibaren Filistin Milli Meclisi ve FKÖ merkez Komitesi üyeliğinde bulunmuştur. 1969’da Filistin Silahlı Mücadele Komutanlığı kurmay başkanı ve 1970’te Filistin Devrim Kuvvetleri komutan yardımcısı oldu. 1972-1984 yılları arasında ise FKÖ’nün siyasi departmanının genel müdürlüğünü yaptı. 1979-1999 arasında FKÖ Yürütme Komitesinin temsilcisi olarak Ürdün Krallığı’nda bulundu. 1984-1991 yılları arasında FKÖ Merkez Komitesinde bağımsız üye olarak görev aldı. 1991-1993 yılları arasında FKÖ Planlama ve Araştırma Merkezleri genel denetçisi oldu. 1994’ten itibaren Yüksek Emniyet Komitesinin başkanlığını üstlenmiştir. Aynı zamanda İsrail ve FKÖ arasında yapılan Oslo Görüşmeleri’ne ve Wye River Görüşmeleri’ne katılmıştır. Ayrıca Gazze Limanı Operasyonu ve Batı Şeria ile Gazze Şeridi arasındaki Güvenli Geçiş Operasyonu heyetine de başkanlık etti. İsrail ile 1999 yılında yapılan kalıcı anlaşma ile Güvenlik ve Sınırlar Komitesi başkanı seçildi. Yaser Arafat, Filistin Hükümeti içinde bir reform yapma isteği üzerine Abdurrezzak’ı 3 Haziran 2002 yılında Filistin Emniyet Kuvvetlerine koordinatör olarak atadı. Ardından 9 Haziran 2002’de içişleri bakanı oldu ve bu görevini 2002 yılının Ekim ayına kadar sürdürdü. Ağustos 2002 yılında Tel Aviv’de yapılan Birinci Gazze-Beytüllahim Anlaşması’nda Filistin tarafına başkanlık etti ve bu anlaşma sonunda Filistin Hükümetinin, İsrailli sivillere yapılacak saldırıları önlemesi karşılığında İsrail kuvvetlerinin Beytüllahim’den ve Gazze’nin belirli bölgelerinden geri çekilmesi üzerinde mutabık kalınmıştır.  Hizmetlerini tamamlayıp emekliliğe sevk edilen Abdurrezzak El-Yahya’ya 2006 yılında müşir (mareşal) rütbesi ve Kudüs Madalyası verilmiştir. 2007 yılında ise Selam Feyyad başkanlığındaki  hükümete içişleri bakanı olarak atanmıştır. 9 Mart 2020’de Amman’da vefat etmiştir.