В годы изгнания задачи спецслужб в ООП и правительстве Арафата исполняли Отдел безопасности командования (внешняя разведка и контрразведка, охрана руководства ООП) и Особая военная группа (военная разведка палестинской армии). Был в ООП и свой спецназ — диверсионная группа «Хавари» и отряд № 17. И начальники Отдела безопасности Кадцуми и Раджуб, и руководители Особой военной группы Абу-Аббас, Абу-Ияш и Абу-Джихад (убитый в 1988 г. командой «Моссад» на своей вилле в тунисском Сиди-Бусейде) участвовали в террористической войне и были связаны с террористами НФОП, «Сайка» и «Черного сентября». Говорить о них как о спецслужбах вряд ли возможно.
Можно условно считать, что спецслужбы Палестины созданы в 1993 г., когда мирный договор ООП и Израиля в Осло позволил Арафату создать свое мини-государство в Газе и на Западном берегу реки Иордан, а самого Арафата даже на Западе и в США стали официально называть «аль-раис» (президент) Палестины. Тогда и была создана полноценная Служба безопасности (по-арабски: Аль-Мухабарат Аль-Амма) — контрразведка и Тайная полиция. Ее возглавил генерал Раджуб, один из сподвижников Арафата. Последующие начальники Службы безопасности, такие как Дахлаф, Маджейда, Аль-Хинди, Балауи (в годы интифады возглавлял личную охрану Арафата), были выходцами из того же боевого крыла ООП и ее главной фракции «Фатх». Служба безопасности сразу взяла под контроль все стороны жизни в секторе Газа, здесь же разместился и ее главный штаб. Военную разведку Палестины с 1993 г. осуществляет Особая военная группа, подчиненная палестинскому Генеральному штабу и расположенная в Газе на проспекте Дир-Эль-Балаха, ее возглавил Аль-Халед. В 1993 г. выделена отдельная Служба разведки во главе с ветераном ООП Хатабом. В качестве спецназа в Газе сохранены отряд № 17 во главе с Мустафой и группа диверсий «Хавари». Помимо них создан специальный отряд «Танзим», подчиненный Арафату, им руководил Абаят, а после его гибели в 2001 г. — Баргути. При палестинском МВД появился «Антитеррористический взвод» во главе с Абу-Лехи для пресечения внутренних волнений.
«Непримиримые» — ХАМАС, «Ислами-Джихад», НФОП и группы Абу-Нидаля в 1993 г. прокляли Арафата и периодически проводили террористические акции против членов его администрации. На гибель нескольких видных деятелей ООП Служба безопасности при поддержке военной и гражданской разведки ответила непримиримым таким же террором, благо опыта было не занимать. После гибели соратника Арафата Сафтиди от рук членов бригады Абу-Нидаля один из членов руководства абу-нидалевского «Революционного совета», Салех, был выслежен и расстрелян арафатовской охранкой в ливанском Бейруте. В 1998 г. трибун «непримиримых» исламского движения ХАМАС Рантиси обвинил Службу безопасности во главе с Раджубом в ликвидации нескольких лидеров ХАМАС в Газе, в том числе в убийстве в Рамаллахе вожака ХАМАС Шарифа, гибель которого палестинцы пытались представить как акт возмездия «Моссад». Обвинения исламиста не были голословными. Рантиси в ту же ночь арестовала Служба безопасности. После протестов ХАМАС генерал Раджуб лично возглавил в Газе операцию по захвату хамасовских руководителей Мукаддида и Синари, во время которой было убито около десятка членов этой группировки.
В 1993 г. Служба безопасности сумела раскрыть заговор «непримиримых» внутри самой ООП и администрации Арафата. Заговорщики, включая нескольких бойцов охраны Арафата, планировали убить последнего во время его визита в Турцию, а помогал им в организации покушения Иран — главный патрон «непримиримых» палестинцев. По подсказке разведки Турции (МИТ) Балауи, возглавлявший в Службе безопасности отдел госохраны, раскрыл заговор. Заговорщики во главе с телохранителем президента Аль-Килани захвачены отрядом № 17 и после пыток признались, что действовали в контакте с Ираном и группой Абу-Нидаля. Отношения Палестины с Ираном настолько испортились, что в 1997 г. охранники Арафата из Службы безопасности в ходе визита их лидера на международную исламскую конференцию в Тегеране устроили во дворце заседаний кровавую драку с иранской охраной. Тот же Балауи выявил внутри палестинских тайных служб нескольких предателей, работавших на «Моссад» или радикальных террористов; среди разоблаченных были такие высокопоставленные палестинские офицеры, как Садави и Ясин, начальник отдела шифрования Службы безопасности Абу-Гани. Как правило, разоблаченных «кротов» тайно ликвидировали, списывая это на акции израильтян. Давал себя знать многолетний опыт подпольного террора, в котором Раджуб и Балауи когда-то были не последними людьми.
