وفي هذه الفترة بدأ الشيخ في الأعداد وإلى جانبه ثلة من الشباب الصادق، فكانوا النواة الأولى وطليعة العمل الجهادي في الجزائر، وأسس الشيخ بو يعلى "الحركة الإسلامية المسلحة" إلى جانب الشيخ منصوري ملياني والشيخ عبد القادر شبوطي والأخ عز الدين باعة والشيخ بالعيدي الدراجي وغيرهم نسأل الله أن يتقبلهم، وقد كان للغزو السوفيتي لأفغانستان سنة 1979م ووقوف النظام الجزائري إلى جانب حلفاءه الملاحدة دافعًا للحركة لتعلن عن نفسها بعد فترة الإعداد والاستعداد، ونزلت لأول مرة بيانات الحركة تعلنُ الحرب على المصالح السوفيتية، وقد استهدفت بعض الرعايا والمصالح السوفيتية ثأرًا لإخوانهم في أفغانستان، كما كان للعملية النوعية لجماعة الجهاد في مصر باستهدافها للطاغية السادات عظيم الأثر على مجاهدي الحركة، كما كان للأحداث الأليمة على أرض سوريا وما لحق إخواننا هناك في حلب وحماة أبلغ الأثر، خاصةً أن الشيخ كان يكن الحب والاحترام الشديد للشيخ مروان حديد رحمه الله، وقد آلمه كثيرًا استشهاد هذا الأسد الجسور وكان يردد (أنه قلما تتوفر للأمة كفاءات مؤمنة مخلصة مجاهدة أمثال الشيخ مروان) .

وكان الشيخ قد تعرض لمحاولة اغتيال من طرف أعوان النظام في 28/ 04/1982 م ولكن الله قد قدر له النجاة، فودع الشيخ أهله وأبلغهم أنه حان الوقت لدخوله السَرِيّة ولن يخرج منها حيًا، وكان له ذلك، وكانت أول عملية قام بها الشيخ وأشباله استهدفت رمز قوة وبطش النظام "مدرسة الصومعة للشرطة" وهي المسلخ الذي أهينت فيه كرامة المؤمنين وهو بمثابة السجن الحربي بمصر أو سجن تدمر في سوريا.

وكان لاختيار الهدف أبلغ الأثر على النظام وزبانيته، كما رفع معنويات المجاهدين ومكنهم من غنيمة الكثير من الأسلحة الحديثة والمستوردة حديثًا من موسكو وأوروبا الشرقية.

واستمرت العمليات الجهادية خاصةً مع التحاق مجموعات جهادية من الغرب بقيادة الشيخ عثمان ومن الشرق بقيادة الشيخ بلعيدي الدراجي بحركة الشيخ مصطفى، فأصبحت العمليات تنفذ على امتداد القطر الجزائري في الجبال الشامخة وفي وسط المدن.

وكان من مخططات الحركة اغتيال الوزير الأول "الجنرال عبد الغني" واختطاف الرجل الأول في الحزب الوثني "شريف مساعدية" ولكن التنفيذ لم يتم بسبب العمل المباغت لأجهزة الأمن ضد أفراد مجموعة الرصد والأعداد - قيل أن أحدهم وشى بهم - فاعتقل 14 من أفراد السريّة وكُشفت العملية.

وبعد سنوات من العمل الجهادي رأى الشيخ أن يعقد مؤتمر لكافة أبناء التيار الإسلامي الجهادي منه والدعوي، فدعى إليه بعض الرموز الدعوية إلى جانب القيادات الجهادية وذلك لتقييم المرحلة السابقة ووضع استراتيجية مستقبلية بعد 5 سنوات من القتال اشتد فيها عود الحركة، وقد اختار مرتفعات جبال الزبربر بمدينة الأربعاء ولاية البليدة مكانا لهذا اللقاء وذلك لمنعة هذا المكان طبيعيًا وكان اللقاء مقررًا في جانفي 1987، ولكن وكما أخبرنا بعض الإخوة ممن عايشوا الفترة أن واحدًا ممن باعوا أخرتهم بدنيا غيرهم وشى بهم - هذا الشخص يتزعم اليوم ما يسمى بتيار الإسلام السياسي المعتدل وهو مقرب جدًا من أجهزة الاستخبارات بل هو أداتهم الأساسية في خلط كل الأوراق في الجزائر - وكان قد أعطى كافة المعلومات عن اللقاء، فحوصرت المنطقة أيما حصار وطوقت مدينة الأربعاء وجبالها ووديانها بقوات كافية لغزو دولة وشددت التعليمات بغلق كل المنافذ، وأحس شيخنا بما يدور حوله فجمع هيئة أركانه وأبلغ الجميع بالمستجدات وقال لهم مقولة الحسين يوم حاصره فجار العراق، ففاضت العيون بالدمع وبايع الجميع الشيخ على القتال إلى الشهادة.