אל-קאעידה ברצועת עזה - קבוצה פלשתינית נוספת הכריזה רשמית (8.5.06) על הקמת ארגון חדש ברצועת עזה הכפוף לארגון אל-קאעידה. בכרוז שהופץ ברצועה תחת הכותרת "צבא ירושלים - ארגון אל-קאעידה באדמת אל-ריבאט" (שטחי הכינוס לקראת היציאה לג'יהאד) נאמר, כי הצבא האיסלאמי הוקם כמימוש לקריאתם של אוסאמה בן-לאדן, איימן זוואהירי ואבו מוסעב א-זרקאווי.
היעד המוצהר של "צבא ירושלים" הינו מלחמה ללא פשרות ביהודים ("האויב שגזל האדמות") ובנוצרים ("עבדי הצלב"). "שמנו למטרה כל אויב של האיסלאם והמוסלמים, אנו נכה ביד ברזל את כל מסעות הצלב האמריקניים והציוניים, נפוצץ את גופנו בעמדותיהם ונרעיד את האדמה מתחת לרגליהם", נאמר בהודעה. הארגון החדש הבטיח להציג בקרוב את תמונות לוחמי הג'יהאד בתחנות הטלוויזיה על-מנת להוכיח את "רצינות כוונותיו".
אל-קאעידה מנצלת את השלטון האיסלאמי החדש של החמאס, מצב האנדרלמוסיה ברשות הפלשתינית וצפיפות האוכלוסיה על-מנת להקים תאים ברצועת עזה. הפעילות בשטחי הרשות הפלשתינית הינה חלק מהשינוי האסטרטגי במדיניות אל-קאעידה המפנה מזה מספר חודשים את מאמציה להקים תשתית ארגונית ענפה גם באזור "אל-שאם" (סוריה, לבנון, ירדן וישראל). לצורך זה מינתה אל-קאעידה אחראי מטעמה ("אמיר") על אזור "אל-שאם" לו כפופים הפעילים באזור כולו.
עובדת הימצאותם של פעילי אל-קאעידה בשטחי הרשות הפלשתינית ידועה זה מכבר. באוגוסט 2000 חשף השב"כ רשת טרור מסועפת הקשורה לארגון אל-קאעידה בראשה עמד נביל עוכל, פעיל חמאס מרצועת עזה, שבמהלך השנים 97-98 עבר אימונים צבאיים במחנות של רב המחבלים אוסאמה בן-לאדן, בפקיסטן ובאפגניסטן.
ביולי 2005 שגרה חוליה של אל-קאעידה רקטות קסאם לעבר נווה דקלים ואף הפיצה סרטו וידאו המתעד את פעולותיה. ב- 7 באוקטובר פרסמה סוכנות הידיעות הפלשתינית "מען" כרוז שהופץ בחאן יונס, ובו מודיע ארגון אל-קאעידה על הקמת שלוחה ברצועת עזה.
לא מכבר עצרו גורמי הביטחון הישראלים שני פעילי אל-קאעידה משכם. נגד השניים, עזאם אבו אל-עדס ובלאל חפנאווי, הוגש כתב אישום על גיוס פעילים לבצע פיגועים מטעם אל-קאעידה ורקימת תוכנית לבצע פיגוע משולב של מחבל מתאבד ומכונית תופת בירושלים. פעילי החוליה שהופעלה על-ידי תשתית אל-קאעידה בירדן נעצרו בידי גורמי הביטחון הישראלים ב-10 בדצמבר 2005 נעצרו בגשר אלנבי, בשובם מירדן.
