وفي عام ١٣٣٠ عزم على الرحلة إلى بلاد الحجاز لأدار فريضة الحج، وفي المدينة المنورة لقي شيخه حمدان الونيسي الذي كان قد هاجر إليها، وقد ألقى بعض الدروس في المسجد النبوي، والتقى بأحد علماء الهند الشيخ حسين أحمد وتلقى عليه بعض العلوم، وكان الشيخ الونيسي قد طلب من ابن باديس الإقامة معه بالمدينة، ولكن الشيخ حسين أحمد أشار عليه بالعودة إلى الجزائر والقيام بنشر العلم في ربوعها، وممن التقى بهم في المدينة الشيخ البشير الإبراهيمي الجزائري الذي تبادل معه البحث في أحوال الجزائر وحاجتها إلى الإصلاح، وقد أصبح فيما بعد زميلا له في عمله في جمعية العلماء الجزائريين.
وبعد أن أمضى ابن باديس نحو عامين في الحجاز توجه نحو بلاد الشام، فزار بيت المقدس ودمشق وغيرهما من المدن الشامية، وقفل راجعا إلى الجزائر مارا بالقاهرة حيث التقى فيها بالشيخ محمد بخيت المطيعي مفتي الديار المصرية وهو من العلماء المصلحين وتلقى عليه وأجازه.
عودته إلى الجزائر:
وحين عاد إلى الجزائر عام ١٣٣٢ أقام في مسقط رأسه قسنطينة، وكان قد بلغ الخامسة والعشرين من عمره، فشرع في وضع خطة العمل في ذلك الجو المظلم من الاستعمار الغاشم الذي كان يفرض أسطورة الجزائر الفرنسية، وفي الوقت الذي نجح فيه الفرنسيون في اصطياد بعض الناس من محترفي السياسة الجزائريين قام ابن باديس بالعمل الهادئ لمحاصرة فرنسا في عزم ولين، من غير أن يلفت الأنظار أو يثير العقبات، فبدأ بإعداد جيل صالح ينهض بالجزائر نهضة إسلامية عربية، وشرع بالتدريس في الجامع الكبير بقسنطينة، ولكن الحكومة الفرنسية منعته من التعليم فيه بسعي المفتي في ذلك العهد الشيخ المولود ابن الموهوب، فسعى أبوه لدى الحكومة الفرنسية وكان ذا جاه عندها فسمحت لولده عبد الحميد بن باديس بالتدريس في الجامع الأخضر بقسنطينة.