In the 21^st century, discourse on the role of non-state actors in foreign policy has been growing and many scholars recognise that non-state actors such as Non-Governmental Organisations (NGOs) are one of the forces that could contribute to the foreign policy making process. Arguably, the attitude of Malaysian leaders as well as the support of Malaysian that favour Palestinians has led to the proliferation and establishment of numerous Muslim faith-based NGOs. These NGOs subsequently play a momentous role in enhancing the bilateral relationship between Malaysia and Palestine. This paper explores this claim by studying the roles of Aqsa Syarif Berhad, a Malaysian Islamic faith-based NGO. It also attempts to assess the contributions of this NGO to Palestine as well as its role in shaping the future direction of Malaysia foreign policy towards Palestine. The paper contends that the role played by Malaysian NGOs has contributed to the enhancement of bilateral relations between Malaysia and Palestine as well as strengthened Malaysia's stand on Palestine.