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