خفية - وبدون ان يعلم أحدا بوجهته - وذلك في آخر شهر تشرين الأول - أكتوبر - ١٨٧٠. واستقبلته السلطة الرسمية التونسية بحفاوة، ومنحه الباي محمد الصادق (نيشان الافتخار التونسي) في ١٨ تشرين الثاني - نوفمبر -. وتظاهر (محيي الدين) بالانصراف لدراسة المخطوطات العربية - الإسلامية في تونس، وتجنب الاتصال بالناس - قدر المستطاع، واكتفى بتحرير نحو المائتي رسالة لزعماء الجزائر حتى (يستعدوا لمحاربة فرنسا عند قدومه إليهم، وأرسلها بصورة سرية مع المرسلين). غير أن أجهزة الاستخبارات الإفرنسية المتعاونة مع الاستخبارات التونسية شعرت بنشاطه الخفي على ما يظهر. فغادر (محيي الدين) تونس إلى مالطا، وعاد فاتجه نحو طرابلس الغرب، ومنها إلى توزر، ونفطة ونغزاوة، متنكرا في ثياب مغربية، ومعه عدد من إخوانه المجاهدين. وعند ذلك أصدرت السلطة التونسية بتحريض من الاستخبارات الإفرسة أوامرها إلى ولاة الأقاليم وأجهزة الشرطة بمطاردته واعتقاله. واستطاعت السلطات التونسية اكتشاف قافلة من أهل سوف كانت متجهة إلى الجزائر، ومعها كمية من البارود وزنها (٦٣) رطلا، فصادرتها منهم. غير أن (محيي الدين) استطاع الوصول إلى منطقة الحدود، حيث التف حوله عدد كبير من الجزائريين اللاجئين أو المنفيين إلى تونس، ومنهم ابن ناصر بن شهرة الذي كان متمردا ثائرا ضد السلطات الإفرنسية منذ العام ١٨٥١، واستقر في (نفطة) وجعل منها قاعدة لجهاده ضد الإفرنسيين، متنقلا ما بينها وبين نغزاوة والجريد. كما انضم إليه الشيخ سليمان بن جلاب السلطان السابق في (تقرت) والذي أبعد إلى هناك منذ العام ١٨٥٤.
وكذلك الشيخ إبراهيم بن عبد الله، مقدم إخوان عبد القادر الجيلالي (بورقلة) والشيح مصطفى بن عزوز، مقدم زاوية