1929da Hayfa yakınlarında Tanturada doğan Abdel Razzak Yahya, askeri strateji üzerine lisans eğitimi almış ve daha sonra Şam Askeri Üniversitesinde Askerlik Bilimi üzerine yüksek lisans yapmıştır. 1967 Arap-İsrail savaşları sırasında Suriye ordusunda harekât subayı olarak görev yapmış olan Yahya o dönemde Şam savunmasının kilit isimlerindendir.
1969-1972 yılları arasında Filistin Kurtuluş Örgütü (FKÖ) ordusunun başkomutanlığını yapan Yahya, daha sonra FKÖ Yönetim Kurulunun askeri danışmanı olarak göreve getirilmiştir. 1993 Oslo Anlaşmasından itibaren İsrail-Filistin barış müzakerelerinin içinde yer almış, İsrail ile gerçekleştirilen birçok güvenlik komitesi toplantısında bulunmuş ve 1993-1995 yıllarında güvenlik komitesine başkanlık yapmıştır. Ayrıca 1999da İsrail ile yapılan görüşmelerde Güvenlik ve Sınırlar Komitesi Başkanlığını yürütmüştür.
2002de Arafat tarafından Filistin Güvenlik Güçleri Koordinasyon Başkanlığına getirilmiş olan Yahya aynı dönemde İçişleri Bakanı olarak atanmıştır.
Görevdeyken güvenlik konularında reform yapmak istemesi ve Arafatın buna karşı çıkması üzerine bakanlık görevinden istifa etmiştir. Daha sonra tekrar göreve gelen Yahya, 2002-2007 yılları arasında Filistin Özerk Yönetimi İçişleri Bakanlığı görevinde bulunmuştur. Hamasın İsraile karşı canlı bombalar ile yaptığı saldırıları kınayan Yahya, FKÖ ordusunun başkomutanlığını yürütmüş ve uzun süre askeri danışmanlık yapmış olmasına karşın direnişin sivil karaktere sahip olması gerektiğini savunmaktadır. 2006 yılında Abdul Razzaq Al-Yahya Siyaset ve Militarizm Arasında adlı hatıralarından oluşan kitabı
çıkmıştır.