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