كان محي الدين بالإضافة لكونه شيخ الطريقة القادرية ذو مكانة رفيعة بين عامة الناس ومن كبار أعيانهم وقد دفعت آراؤه بالحاكم العثماني لوهران إلى تحديد إقامته ببيته وهو ما دفعه للتفكير بالخروج لأداء فريضة الحج والابتعاد عن هذا الجو المشحون.
أذن لمحي الدين بالخروج لفريضة الحج عام 1241 هـ/ 1825م، فخرج واصطحب ابنه عبد القادر معه وهو في سن الثامنة عشرة، فكانت رحلة عبد القادر إلى تونس ثم مصر ثم الحجاز ثم البلاد الشامية ثم بغداد، ثم العودة إلى الحجاز، ثم العودة إلى الجزائر مارًا بمصر وبرقة وطرابلس ثم تونس، وأخيرًا إلى الجزائر من جديد عام 1828 م، فكانت رحلة تعلم ومشاهدة ومعايشة للوطن العربي في هذه الفترة من تاريخه، وما لبث الوالد وابنه أن استقرا في قريتهم "قيطنة"، ولم يمض وقت طويل حتى تعرضت الجزائر لحملة عسكرية فرنسية شرسة، وتمكنت فرنسا من احتلال العاصمة فعلاً في 5 يوليو 1830م، واستسلم الحاكم العثماني الداي حسين، ولكن الشعب الجزائري كان له رأي آخر.
تلقى الشاب مجموعة أخرى من العلوم فقد درس الفلسفة (رسائل إخوان الصفا - أرسطوطاليس - فيثاغورس) ودرس الفقه والحديث فدرس صحيح البخاري وصحيح مسلم، وقام بتدريسهما، كما تلقى الألفية في النحو والسنوسية والعقائد النسفية في التوحيد، وايساغوجي في المنطق، والإتقان في علوم القرآن، وبهذا اكتمل للأمير العلم الشرعي، والعلم العقلي، والرحلة والمشاهدة.