Mendirikan Fatah dan PLO
Meski terbilang sukses sebagai kontraktor, panggilan jiwanya yang lain yakni untuk membela Palestina tetap hidup. Ia lalu bergabung dengan gerilyawan pembela Palestina dengan nama samaran "Abu Ammar". Â Pergaulan dan persahabatan yang baik dengan banyak pejuang, mengantarkan dirinya dan sahabat-sahabatnya menginisiasi pendirian Fatah pada 1958. Organisasi yang mengajak orang-orang Palestina melawan Israel ini juga memiliki jaringan bawah tanah. Sahabat seperjuangan Yasser Arafat dalam organisasi ini meninggalkan Palestina sejak 1948 pasca proklamasi negara Israel di wilayah Palestina. Enam tahun mengorganisir Fatah, Yasser Arafat mulai berani merancang serangan atau sabotase melawan Israel dari basis Fatah di Yordania, Lebanon, dan Mesir-Gaza.
Yasser Arafat tidak hanya merintis Fatah, organisasi ini juga menjadi unsur penting bersama Liga Arab saat mendirikan organisasi pembebasan Palestina yang lebih dikenal dengan nama Palestine Liberation Organization (PLO) pada 1964. Organisasi ini didirikan sebagai hasil Muktamar Umum Rakyat Palestina (28 Mei-2 Juni 1964) di Al-Quds. Tiga tahun berselang---setelah dua pemimpin PLO---barulah Yasser Arafat memimpin organisasi ini.
PLO dalam perkembangannya tidak hanya bergerak di bidang militer tetapi juga politik. Di bidang politik ini, Yasser Arafat bertekad agar dunia mengetahui bahwa perjuangan rakyat Palestina adalah satu perang pembebasan nasional yang dilancarkan dengan dukungan negara-negara lain, termasuk Uni Soviet dan PBB.
Dengan demikian, Yasser Arafat memiliki dua organisasi untuk membela Palestina yaitu Fatah dan PLO. Maka tidak mengherankan jika ia mulai menjadi sosok yang populer dengan kedua organisasi tersebut. Terbukti saat diselenggarakan pemilihan oleh Dewan Nasional Palestina, Fatah berhasil memenangkan pemilihan. Ini berarti Yasser Arafat semakin memiliki kewenangan menyebarkan semangat kebebasan yang menjadi misi utama PLO. Lebih luas PLO juga mengurusi hal-hal yang berkaitan dengan kesejahteraan, kesehatan, pendidikan, informasi dan keamanan.
Bergerilya dan Perang Terbuka dengan Israel
Bertepatan dengan kepemimpinan Arafat dalam PLO, meletus perang enam hari antara Israel dengan Mesir yang berakhir dengan kekalahan Mesir. Sekitar sepekan setelah kekalahan ini, Yasser Arafat kembali memakai keterampilan militernya di bagian sabotase sehabis kuliah dulu. Ia menyamar untuk melintasi Sungai Yordan untuk memasuki Tepi Barat. Ia berhasil mendirikan pusat perekrutan anggota baru di Hebron, sekitar Yerusalem dan Nablus. Ia juga mulai menggalang simpati pejuang dan sekaligus menyumbang untuk perjuangan.
Keberanian dan ketangguhan Yasser Arafat sebagai mantan perwira AD Mesir berpangkat Letnan kembali dibuktikan dalam Perang Karameh (1969). Karameh adalah nama sebuah desa di Yordania yang menjadi target operasi besar Israel. Di desa ini terdapat markas Fatah pimpinan Yasser Arafat dan sebuah kamp pengungsi Palestina berukuran sedang. Mendengar adanya rencana operasi besar Israel ke desa ini, beberapa kelompok milisi memutuskan mundur. Tetapi berbeda dengan Fatah, Yasser Arafat meyakinkan pasukannya untuk bertahan. Ia bertekad meyakinkan dunia bahwa ada satu kelompok dari dunia Arab yang tidak akan mundur dan melarikan diri. Tekad kuat Yasser Arafat menghadapi Israel menarik simpati Angkatan Darat Yordania untuk membantu.
Malam 21 Maret, Israel melancarkan serangan darat dan udara dengan persenjataan berat seperti lapis baja dan jet tempur. Saat Israel mengintensifkan serangan, militer Yordania memasuki kancah peperangan seperti telah mereka janjikan. Tak ingin konflik meluas, Israel terpaksa menarik diri. Meski lebih banyak milisi Fatah yang gugur, tetapi penarikan diri pasukan Israel telah mengorbitkan nama Yasser Arafat sebagai pahlawan Palestina yang berani menghadapi Israel.
